POJ 1064 Cable master
解説
蟻本に解法が載ってある。
二部探索まだまだ身についてない。
#include <iostream> #include <cmath> using namespace std; const int INF = 1 << 29; int n,k; double l[10001]; bool C(double x){ int num = 0; for(int i = 0; i < n; i++) num += (int)(l[i] / x); return num >= k; } int main(){ cin >> n >> k; for(int i = 0; i < n; i++) cin >> l[i]; double l = 0, r = INF; for(int i = 0; i < 100; i++){ double mid = (l + r) / 2; if(C(mid)) l = mid; else r = mid; } cout << fixed; cout.precision(2); cout << floor(r * 100) / 100 << endl; }