POJ_1064 Cable master
蟻本を参考にした。
二分法で解の存在する幅を狭めていく。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int N, K; double L[MAX_N]; bool c(double t){ int s = 0; for(int i = 0; i < N; i++){ s += (int)(L[i] / t); } return s >= K; } int main(){ scanf("%d %d", &N, &K); for(int i = 0; i < N; i++){ scanf("%lf", &L[i]); } double low = 0.0, high = 1000000.0; for(int i = 0; i < 100; i++){ double ave = (low+high) / 2.0; if(c(ave)) low = ave; else high = ave; } printf("%.2f\n", (double)((int)(high * 100.0)) / 100.0); return 0; }