程序员人生 网站导航

北大ACM1064――Cable master

栏目:综合技术时间:2015-06-06 08:16:25

题目主要的意思是:有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; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐