POJ 2976: Dropping Tests

概要

授業でn回のテストを受けた.i番目のテストではb[i]問中a[i]問正解した.
受けたテストのうちk回を取り除き, 100 \cdot (\sum_i a_i) / (\sum_i b_i)を最大化したい.

解法

二分探索.蟻本の練習問題まんま.

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));
    }
}