51nod-1257-背包问题V3（0/1分数规划）

题目链接：http://www.51nod.com/Challenge/Problem.html#problemId=1257

题目大意：中文题。

思路：0/1分数规划的入门。由于答案用分数表示。因此我们需要另开一个数组记录二分到Ans时的分子和分母，然后化简即可。

ACCode：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=5e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

struct Score{
	ll A,B;
	double Ans;
	Score(ll _A=0,ll _B=0,double _Ans=0.0){
		A=_A;B=_B;Ans=_Ans;
	}
	ll GCD(ll a,ll b){
		if(b==0) return a;
		else return GCD(b,a%b);
	}
	Score Reduction(){
		ll res=GCD(A,B);
		A/=res;B/=res;
	}
	friend int operator < (Score a,Score b){
		return a.Ans>b.Ans;
	}
};
Score V[MAXN],Ans;
int n,k;

int Judge(double mid){
	for(int i=1;i<=n;++i){
		V[i].Ans=1.0*V[i].A-1.0*mid*V[i].B;
	}sort(V+1,V+1+n);
	double Sum=0.0;
	Ans=Score(0,0);
	for(int i=1;i<=k;++i){
		Sum+=V[i].Ans;Ans.A+=V[i].A;Ans.B+=V[i].B;
	}Ans.Reduction();
	if(Sum>0) return 1;
	else return 0;
}
int main(){
	//printf("!\n");
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&V[i].B,&V[i].A);
	}
	double l=0,r=50000,mid;
	while(l<r-EPS){
		mid=(l+r)/2.0;
		if(Judge(mid)) l=mid;
		else r=mid;
	}printf("%lld/%lld\n",Ans.A,Ans.B);
}