学步园

poj 2976 Dropping tests

题意同
poj 3111 (只有一点点区别 )

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 1000 + 10;
int a[maxn], b[maxn];
struct node {
    double val;
    bool operator < (const node& rhs) const {
        return val > rhs.val;
    }
};

node f[maxn];
int n, k;

//sigma(ai)/sigma(bi) >= x
//-> sigma(ai - x*bi) >= 0
int ok(double x) {
    for(int i=0; i<n; ++i) {
        f[i].val = a[i] - x*b[i];
    }
    sort(f, f+n);
    double sum = 0;
    for(int i=0; i<k; ++i) {
        sum += f[i].val;
    }
    return sum >= 0;
}

int main() {
    while(~scanf("%d%d", &n, &k)) {
        if(n==0 && k==0) break;
        k = n - k;
        for(int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
        }
        for(int i=0; i<n; ++i) {
            scanf("%d", &b[i]);
        }
        double l = 0, r = 1;
        //for(int i=0; i<50; ++i) {
        while(r-l>1e-8) {
            double mid = (l+r)/2;
            if(ok(mid)) l = mid;
            else r = mid;
        }
        printf("%d\n", (int)(l*100 + 0.5) );
        //printf("%.f\n", l*100);  系统默认也是向上取整
    }
    return 0;
}