AcWing 680. 剪绳子
原题链接
简单
作者:
fairydetail
,
2019-04-25 22:15:10
,
所有人可见
,
阅读 1926
C++ 代码
//考虑用二分法来做(找到某种性质的分界点)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],n,m;
bool check(double mid)
{
int sum=0;
for(int i=0;i<n;i++)
{
sum+=a[i]/mid;
}
if(sum>=m) return true;
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
double l=0,r=1e9;
while(r-l>1e-4)//因为此时两数类型为double,所以不直接用r>l
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2f\n",r);
return 0;
}
while(r-l>1e-4)//因为此时两数类型为double,所以不直接用r>l,这句话的判断,为什么要大于1e-4啊
哇
这个是poj原题诶 POJ 1064
厉害了