Mayflyyh
Mayflyyh
MayFlyyh's Blog
POJ 2976 Dropping tests

给定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;
}

本文链接:http://www.mayflyyh.com/archives/283
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      二分答案      POJ 2976 Dropping tests
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

POJ 2976 Dropping tests
给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i])) 其中a,b都是一一对应的。 x[i]取0,1 并且 ∑x[i] = n …
扫描二维码继续阅读
2018-07-16