POJ-2976, ZOJ-3068 : Dropping tests
問題概要
平均値の最大化。
acceptされたコード
計算量O(N*log N * 二分探索)。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 1000; double X; int N, K; int ws[MAX_N], vs[MAX_N], ids[MAX_N]; bool init(){ scanf("%d%d", &N, &K); for(int i=0; i<N; i++){ scanf("%d", vs+i); } for(int i=0; i<N; i++){ scanf("%d", ws+i); ids[i] = i; } return N > 0; } bool cmp(int i, int j){ return vs[i] - X*ws[i] > vs[j] - X*ws[j]; } bool check(double x){ X = x; sort(ids, ids+N, cmp); double total = 0.0; for(int i=0; i<N-K; i++){ total += vs[ids[i]] - X*ws[ids[i]]; } return total <= 0.0; } int solve(){ double low = 0.0, high = 1.0; for(int loop=0; loop<20; loop++){ double mid = (high + low) / 2.0; if(check(mid)){ high = mid; } else{ low = mid; } } return (int)(100 * low + 0.5); } int main(){ for(;init();){ printf("%d\n", solve()); } return 0; }