题意:
有N条绳子,他们的长度分别为Li,如果从他们中切割出K条长度相同的绳子的话,这K条绳子每条能最长能多长?答案 保留小数点后两位。
题解:
判断可行性,很明显的二分搜索。寻找最大的L,满足能切割出K条绳子!
题目虽然简单,但是体现了二分搜索的基本思想和编程风格(这里是浮点数,所以怎么循环还是要注意的,简单粗暴的就是直接循环100次)。
注意:这里的保留小数点后两位,并不是四舍五入,而是向下取整!
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int N,K;
double L[10005];
const int INF=1e5+5;bool C(double x)
{int num=0;for(int i=0; i<N; i++)num+=L[i]/x;return num>=K;//可行解
}void solve()
{double lb=0, ub=INF;for(int i=0; i<100; i++)//100次精度以及很高了,一般的浮点都这样操作就可以!{double mid=(lb+ub)/2;if(C(mid))lb=mid;//可行解给lb!一直找,找到最大为止。else ub=mid;}printf("%.2f\n",floor(lb*100)/100);//向下取整!直接.2是四舍五入
}
int main()
{cin>>N>>K;for(int i=0; i<N; i++)cin>>L[i];solve();
}