Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1064 Cable master 二分搜索

Posted on 2010-12-21 12:54 Onway 阅读(840) 评论(0)  编辑 收藏 引用 所属分类: 伤不起的ACM
/*
pku 1064 Cable master
http://poj.org/problem?id=1064
题目分类:二分搜索
题意:给出n根不同长度的电缆,要求将这些电缆分割成长度最大且相同的m根。
思路:由题目给出的数据规模,最大长度在1厘米到100公里(1千万厘米)之间,
可以二分搜索最大长度。
总结:由于对二分不熟悉,也是看了别人的提示才想到切入点。有了切入点后,
这个题目基本上就算是水题了。写出来交上去居然是果断的WA,在discuss看了
很多人都说是卡精度。改了几次交上去还是WA,后来自己出的数据发现,原来是
二分的一个变量赋值搞错了。
二分的思路很简单,但细节很多,很容易就会写错。
*/
#include 
<iostream>
#include 
<iomanip>
using namespace std;
const int MAX=10000;
const int LARGE=10000000;
int cable[MAX+1];

int n,m;
int cut(int len)
{
    
int i,sum=0;
    
for(i=1;i<=n;++i)
        sum
+=cable[i]/len;
    
return sum;
}

int main()
{
    
int i;
    
double tmp;
    scanf(
"%d%d",&n,&m);
    
for(i=1;i<=n;++i)
    {
        scanf(
"%lf",&tmp);
        cable[i]
=int(tmp*100);
    }
    
//end input
    int left=1,right=LARGE,mid,ans=0;
    
do
    {
        mid
=(left+right)/2;
        
if(cut(mid)<m)
            right
=mid-1;
        
else
        {
            ans
=mid;
            left
=mid+1;
        }
    }
while(right>=left&&right>0);
    cout
<<setiosflags(ios::fixed)<<setprecision(2)<<double(ans/100.0)<<endl;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理