POJ 2976: Dropping Tests
概要
授業でn回のテストを受けた.i番目のテストではb[i]問中a[i]問正解した.
受けたテストのうちk回を取り除き,を最大化したい.
解法
二分探索.蟻本の練習問題まんま.
int n, k; int a[1010], b[1010]; double v[1010]; bool C(double x){ for(int i = 0; i < n; ++i) v[i] = 100LL * a[i] - x * b[i]; sort(v, v + n); double sum = 0; for(int i = k; i < n; ++i){ sum += v[i]; } return sum >= 0; } main(){ for(;;){ scanf("%d%d", &n, &k); if( n == 0 && k == 0 ) return 0; for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); } for(int i = 0; i < n; ++i){ scanf("%d", &b[i]); } double lb = 0, ub = 100; for(int i = 0; i < 100; ++i){ double mid = (lb + ub) / 2; if(C(mid)){ lb = mid; } else{ ub = mid; } } printf("%d\n", (int)floor(lb + 0.5)); } }