poj 2976 Dropping tests (二分查找)

本文主要是介绍poj 2976 Dropping tests (二分查找)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于(a1+a2+....an)/(b1+b2........bn)=x，可以去掉其中k个数据 ，求x的最大值。

其实可以二分查找答案，我们只需要判断当平均分为x时，可不可行。

我们可以对上面的式子进行变形。。。。

a1+a2+.....an>=b1*x + b2*x +.......bn*x

继续变形。。。

(a1-b1*x)+(a2-b2*x)+.......(an-bn*x)>=0;

我们令c1=(a1-b1*x)   c2=(a2-b2*x)    ....cn=(an-bn*x)

对c1,c2,...cn进行排序，只取最大的n-k个之和，判断是否大于0。。。

PS:对于输出距离最近的整数，我们可以把答案加上0.5，然后取整（强制转化成int）,就是答案，

比如83.3加上0.5=83.8 取整=83      比如是83.6 加上0.5=84.1  取整=84

#include<stdio.h>
#define exp 1e-3
#define N 1000+16
int n,k;
double c[N],a[N],b[N];
void qsort(double a[],int l,int r)//快速排序
{int i,j;double x;if(l<r){i=l;j=r;x=a[i];while(i<j){while(i<j&&a[j]<=x)j--;if(i<j)a[i++]=a[j];while(i<j&&a[i]>x)i++;if(i<j)a[j--]=a[i];}a[i]=x;qsort(a,l,i-1);qsort(a,i+1,r);}return ;
}
int judge(double x)//判断平均分为x时，可不可行
{int i;double sum=0;for(i=0;i<n;i++){c[i]=100*a[i]-x*b[i];}qsort(c,0,n-1);for(i=0;i<n-k;i++){sum+=c[i];}return sum>=0;
}
int main(void)
{int i;double l,r,m;while(~scanf("%d%d",&n,&k)&&n+k!=0){for(i=0;i<n;i++)scanf("%lf",&a[i]);for(i=0;i<n;i++)scanf("%lf",&b[i]);l=0;r=100;while(r-l>exp)//二分查找{m=(l+r)/2;if(judge(m))l=m;elser=m;}printf("%d\n",(int)(l+0.5));		}
}

 

 

这篇关于poj 2976 Dropping tests (二分查找)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---