北大ACM1064――Cable master
來源：程序員人生 發布時間：2015-06-06 08:16:25 閱讀次數：4129次
題目主要的意思是：有N條繩子，它們的長度分別為Li，如果從它們中切出K條長度相同的繩子的話，這K條繩子每條的最長的長度能是多少？
這1題用2分搜索可以很好的進行求解。
長度分別為0到INF（INF為盡量大的數）。然落后行2分搜索，不斷的縮小范圍，循環1定的次數，可以很好的將答案求出。
G++double要用%lf輸入，用%f輸出，C++是window下的，用%lf輸入，用%lf輸出。
下面是AC的代碼：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int INF = 10005;
const int MAX_N = 10005;
int N, K;
double Len[MAX_N];
bool C(double x)
{
int num = 0;
for(int i = 0; i < N; i++)
{
num += (int)(Len[i] / x);
}
return num >= K;
}
void solve()
{
double lb = 0.0, ub = (double)INF * 10.0, mid;
for(int i = 0; i < 100; i++) //循環1百次，可以足夠求解了
{
mid = (lb + ub) / 2;
if(C(mid))
lb = mid;
else
ub = mid;
}
printf("%.2f
", floor(ub * 100) / 100); //注意，這里需要用G++提交，如果是C++提交的話，改成%.2lf。
}
int main()
{
int i;
while(scanf("%d%d", &N, &K) != EOF)
{
for(i = 0; i < N; i++)
scanf("%lf", &Len[i]);
solve();
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
