AcWing 680. 剪绳子
原题链接
简单
作者:
尼古拉斯小布丁
,
2021-01-31 21:38:46
,
所有人可见
,
阅读 352
写法一
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int w[N];
bool check(double mid){
int cnt =0 ;
for(int i=0;i<n;i++){
cnt += w[i] / mid;
}
return cnt >= m;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[i];
double l = 0, r= 1e9;
while(r-l>1e-4){
double mid = (l+r) / 2;
if(check(mid)) l=mid;
else r =mid;
}
printf("%.2lf\n",r);
return 0;
}
写法2
浮点数二分循环次数:10^7/N,即10的7次方除以check函数执行的次数
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int w[N];
bool check(double mid){
int cnt =0 ;
for(int i=0;i<n;i++){
cnt += w[i] / mid;
}
return cnt >= m;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[i];
double l = 0, r= 1e9;
for(int i=0;i<100;i++){
double mid = (l+r) / 2;
if(check(mid)) l=mid;
else r =mid;
}
printf("%.2lf\n",r);
return 0;
}