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
#include
#include
#include
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

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

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

发表评论

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

Ɣ回顶部