Posted on 2010-12-21 12:54
Onway 阅读(816)
评论(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;
}