当前位置: 代码迷 >> 综合 >> POJ---1064(Cable master,简单二分判断可行性)
  详细解决方案

POJ---1064(Cable master,简单二分判断可行性)

热度:28   发布时间:2024-01-22 02:05:38.0

题意:

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();
}


  相关解决方案