POJ 2976 Dropping tests

作者: MayFlyyh 分类: 二分答案 发布时间: 2018-07-16 14:15 ė 6 没有评论

给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i])) 其中a,b都是一一对应的。 x[i]取0,1 并且 ∑x[i] = n – k。


看到除法,应该是分数规划吧。每次二分以后计算出一串数字对答案的贡献大小,从小到大排序选前n-k个。如果都大于0就说明还可以选择一个更好的分数。注意一下精度,这场CF挂了很多精度有问题的人

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
int a[2000],b[2000];
int n,k;
double c[2000];
inline int check(double mid){
    for(int i=1;i<=n;++i){
        c[i]=a[i]-b[i]*mid;
    }
    std::sort(c+1,c+1+n);
    double sum=0;
    for(int i=k+1;i<=n;++i){
        sum+=c[i];
    }
    return sum>0;
}
int main (){
    while(scanf("%d %d",&n,&k)){
        if(n==0) break;
        for(int i=1;i<=n;++i)scanf("%d",&a[i]);
        for(int i=1;i<=n;++i)scanf("%d",&b[i]);
        double l=0,r=1.1;
        while(l+0.00001<r){
            double mid=(l+r)*0.5;
            if(check(mid))l=mid;
            else r=mid;
        }
        printf("%.0lf\n",1.0*l*100);
    }

    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/283

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部