luoguP2989 [USACO10MAR]对速度的需要Need For Speed

Isonan · 2018-08-12 10:21:42 · 题解

原题传送门>Here<

我的01分数规划学习笔记>Here<

这题是一道01分数规划问题，二分和判定的方法都比较常规，每次二分mid时判断能不能使选出的数之和为负数就可以了。对于要求的满足比率最大的条件下使重量最小，只要双关键字排序以后选择就可以了。在二分时顺便存一下选中的零件，最后输出就好了。

代码如下：

#include <cstdio>
#include <algorithm>

struct point{
    double val;
    int pos,m;
}num[10001];
bool cmp(point a,point b){
    return a.val==b.val ? a.m<b.m : a.val<b.val;
} 
double F[10001],M[10001],l,r,mid;
int n,ans[10001],top,tem[10001],ttop;
bool judge(double u){
    for(int i=0;i<=n;i++)num[i].val=M[i]*u-F[i],num[i].m=M[i],num[i].pos=i;
    std::sort(num+1,num+n+1,cmp);
    ttop=0;
    for(int i=1;num[0].val>0.0&&i<=n;i++)tem[++ttop]=num[i].pos,num[0].val+=num[i].val;
    if(num[0].val>0.0)return 0;
    top=ttop;
    for(int i=1;i<=top;i++)ans[i]=tem[i];
    return 1;
}
int main(){
    scanf("%lf%lf%d",F,M,&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",F+i,M+i);
    l=0.0,r=10000000.0;
    while(r-l>=0.0001){
        mid=(l+r)/2;
        if(judge(mid))l=mid;
        else r=mid;
    }
    std::sort(ans+1,ans+top+1);
    for(int i=1;i<=top;i++)printf("%d\n",ans[i]);
    if(!top)puts("NONE");
}