题解：P10505 Dropping Test

PengDave · 2024-06-06 22:36:32 · 题解

solution

考虑二分答案。可得（下面式子中的 a 和 b 均表示去掉 k 门考试成绩的 a 和 b）：

去分母、移项得：

很显然，只要贪心地保留 a_i-b_i\times mid 最大的 n-k 门考试成绩即可。

code

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k;
double a[1010],b[1010],tmp[1010];
bool check(double m){
    double cnt=0;
    for(int i=1;i<=n;i++){
        tmp[i]=a[i]-b[i]*m;
    }
    sort(tmp+1,tmp+1+n);
    for(int i=n;i>k;i--){
        cnt+=tmp[i];
    }
    return cnt>=0.0;
}
const double eps=1e-8;
int main(){
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    while(cin>>n>>k){
        if(n==0&&k==0){
            break;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        double st=0,ed=100;
        while(fabs(ed-st)>=eps){
            double mid=st+(ed-st)/2.0;
            if(check(mid)){
                st=mid;
            }else{
                ed=mid;
            }
        }
        cout<<round(st*100.0)<<"\n";
    }
    cout<<flush;
    return 0;
}