01分数规划

http://www.51nod.com/Challenge/Problem.html#problemId=1257

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int maxn=4e5+8;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+7;
const ULL base=1e7+7;
const int maxp=26+5;
using namespace std;
int w[maxn],p[maxn];
pair<double,int> d[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&p[i]);
    }
    double l=0.0,r=50001.0;
    double mid;
    double sz;
    LL fz,fm;
    while(l+eps<=r){
        mid=(l+r)/2.0;
        sz=0.0;
        for(int i=1;i<=n;i++){
            d[i].fi=(double)p[i]-mid*w[i];
            d[i].se=i;
        }
        sort(d+1,d+1+n);
        for(int i=n;i>=n-k+1;i--){
            sz+=d[i].fi;
        }
        if(sz>=eps){
            fm=0;
            fz=0;
            for(int i=n;i>=n-k+1;i--){
                fm+=p[d[i].se];
                fz+=w[d[i].se];
            }
            l=mid;
        }
        else{
            r=mid;
        }
    }
    LL g=__gcd(fm,fz);
    fm/=g;
    fz/=g;
    cout<<fm<<'/'<<fz<<endl;
}