Posted on 2010-12-21 12:54
Onway 閱讀(870)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
/*
pku 1064 Cable master
http://poj.org/problem?id=1064
題目分類：二分搜索
題意：給出n根不同長(zhǎng)度的電纜，要求將這些電纜分割成長(zhǎng)度最大且相同的m根。
思路：由題目給出的數(shù)據(jù)規(guī)模，最大長(zhǎng)度在1厘米到100公里（1千萬(wàn)厘米）之間，
可以二分搜索最大長(zhǎng)度。
總結(jié)：由于對(duì)二分不熟悉，也是看了別人的提示才想到切入點(diǎn)。有了切入點(diǎn)后，
這個(gè)題目基本上就算是水題了。寫出來(lái)交上去居然是果斷的WA，在discuss看了
很多人都說(shuō)是卡精度。改了幾次交上去還是WA，后來(lái)自己出的數(shù)據(jù)發(fā)現(xiàn)，原來(lái)是
二分的一個(gè)變量賦值搞錯(cuò)了。
二分的思路很簡(jiǎn)單，但細(xì)節(jié)很多，很容易就會(huì)寫錯(cuò)。
*/
#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;
}