01分数规划入门题

这道题有非常经典的错误解法：按照pi/wi排序

这样是不能保证答案最大的，反例（本体样例）已经有了

那么我们来考虑怎么做

首先我们二分这个答案ans

让后我们给每个物品i设置一个权值v[i]=p[i]-ans*w[i]

所有物品按照v排序，取前k大求和

那么如果ans是正确答案，那么显然，这个和S=0

如果ans大于正确答案，S<0

如果ans小于正确答案，S>0

发现是满足二分的单调性的，所以这样是对的，复杂度O(n log n log pi)

不过还有一种更加快的迭代的做法

我们将所有物品按照v排序，取前k大的物品计算一下∑pi/∑wi的值res，如果ans和res差别很小就可以直接退出

否则令ans=res，重复上面过程

这个过程感觉很玄学，没有二分清晰，但是跑的很快

我的代码（二分）

#include
    
     #include
     
      #include
      
       #define N 50010#define LL long longusing namespace std;int n,m,w[N],p[N],r[N]; LL x,y,c,a,b; double s[N],l=0,_r=50000;inline bool cmp(int x,int y){
     return s[x]>s[y]; }inline int ok(double k){
        double S=0;    for(int i=1;i<=n;++i) s[r[i]=i]=p[i]-w[i]*k;sort(r+1,r+1+n,cmp);    for(int i=1;i<=m;++i) S+=s[r[i]];    return S>=0;}int main(){
        scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i) scanf("%d%d",w+i,p+i);    for(double M;_r-l>1e-6;ok(M)?l=M:_r=M) M=(l+_r)/2.;    for(int i=1;i<=m;++i) x+=w[r[i]],y+=p[r[i]];    for(a=x,b=y;b;a=b,b=c) c=a%b;    printf("%lld/%lld",y/a,x/a);}