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

题目链接

题目大意就是给定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会使精度损失严重。

---

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1e3+10; 
int n,k,a[N],b[N];;
double eps=1e-7,d[N];
int read()
{
    int ans=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
    return ans*f;
}
/*----------------------------------------------------------*/
int main()
{
    n=read();k=read();
    while(n!=0||k!=0){
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        double l=0,r=1.0,mid;
        while(r-l>eps){
            double sum=0;mid=(l+r)/2;
            for(int i=1;i<=n;i++)d[i]=a[i]-mid*b[i];
            std::sort(d+1,d+1+n);
            for(int i=k+1;i<=n;i++)sum+=d[i];
            if(sum>0)l=mid;
            else r=mid;
        }
        printf("%.0f
",mid*100);
        n=read();k=read();
    }
    return 0;
}