贪心求反例
查看原帖
贪心求反例
663195
Z_AuTwT楼主2024/5/18 11:07
#include<bits/stdc++.h>
using namespace std;
struct node{
    int Yes,Sum;
    double cz;
}arr[1010];
bool cmp(node a,node b){
    if(a.cz!=b.cz) return a.cz<b.cz;
    else return a.Sum>b.Sum;
}
main(){
    int n,k;
    while(cin>>n>>k&&(n||k)){
        for(int i=1;i<=n;i++) cin>>arr[i].Yes;
        for(int i=1;i<=n;i++){cin>>arr[i].Sum;arr[i].cz=1.00*(arr[i].Sum-arr[i].Yes);}
        if(n==k){
            puts("100");
            continue;
        }
        sort(arr+1,arr+n+1,cmp);
        double z=0,m=0;
        for(int i=1;i<=n-k;i++){
            z+=1.00*arr[i].Yes;
            m+=1.00*arr[i].Sum;
        }
        printf("%.0lf\n",100.00*z/m);
    }
}
2024/5/18 11:07
加载中...