分析

找来的 分数规划模板题。我们要求的是 ，所以直接二分 ，那么贪心的选取最大的 个 ，最后再判断 就好了。

代码

// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
LL n,m;
const int N = 1e4 + 100;
LL a[N],b[N];
const double inf = 2e18;
double c[N];
bool check(double mid) {
    for(int i = 1;i <= n;i++) c[i] = a[i] - mid * b[i];
    sort(c+1,c+1+n);double ans = 0;
    for(int i = n;i >= m+1;i--) ans += c[i];
    return ans > 0 ;
}
int main() {
    while(1) {
        n = read();m = read();
        if(!n && !m) break;
        for(LL i = 1;i <= n;i++) a[i] = read() * 100LL;
        for(LL i = 1;i <= n;i++) b[i] = read();
        double l = -inf,r = inf;
        while(r - l > 1e-10) {
            double mid = (l + r) / 2;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%lld\n",(LL)(l+0.5));
    }
    return 0;
}