【POJ2976】Dropping tests——01分数规划

时间:2021-12-15 18:40:35

题目链接

题目大意就是给定n个二元组(a,b),求取n-k个二元组时sigma(a[i])/sigma(b[i])的最大值并输出最大值*100向下取整的答案。

 

 


 

 

很明显的分数规划,因为题目保证ai<=bi所以最大值必然<=1

我们用x[i]来表示i这个二元组取或不取(0为不取,1为取,当然这个数组最后根本不用用到),定义一个函数f(l)=sigma(a[i]*x[i])-l*sigma(b[i]*x[i])=sigma((a[i]-l*b[i])*x[i]),d[i]=a[i]-l*b[i]。

f(l)=sigma(d[i]*x[i])。

当f(l)>0时sigma(a[i]*x[i])-l*sigma(b[i]*x[i])>0,进而sigma(a[i]*x[i])/sigma(b[i]*x[i])>l,也就是说这种方案能使答案比当前l更大;而当f(l)<0时,说明l这个值是取不到的(sigma(d[i]*x[i])不小于0)。

所以我们要求的其实就是f(l)=0时l的值

因为d数组的值是随l的增大而减小的,这样的话由单调性直接二分就好啦。

sort默认是升序的,所以f[l]=sigma(f[i](k+1<=i<=n))。

 


 

 

注意本题的几个特殊地方:

1.只有当读到n和k同时都为0的时候才退出,而不是其中一个为0;

2.输出要用%.0f的方式,强制转成int会使精度损失严重。

 


 

代码:

 

【POJ2976】Dropping tests——01分数规划【POJ2976】Dropping tests——01分数规划
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 const int N=1e3+10; 
 5 int n,k,a[N],b[N];;
 6 double eps=1e-7,d[N];
 7 int read()
 8 {
 9     int ans=0,f=1;char c=getchar();
10     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
11     while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
12     return ans*f;
13 }
14 /*----------------------------------------------------------*/
15 int main()
16 {
17     n=read();k=read();
18     while(n!=0||k!=0){
19         for(int i=1;i<=n;i++)a[i]=read();
20         for(int i=1;i<=n;i++)b[i]=read();
21         double l=0,r=1.0,mid;
22         while(r-l>eps){
23             double sum=0;mid=(l+r)/2;
24             for(int i=1;i<=n;i++)d[i]=a[i]-mid*b[i];
25             std::sort(d+1,d+1+n);
26             for(int i=k+1;i<=n;i++)sum+=d[i];
27             if(sum>0)l=mid;
28             else r=mid;
29         }
30         printf("%.0f\n",mid*100);
31         n=read();k=read();
32     }
33     return 0;
34 }
POJ2976