51nod1257 背包问题 V3

分数规划经典。开始精度1e-3/1e-4都不行，1e-5就A了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
const double eps=1e-5;
const int nmax=5e4+5;
const int inf=0x7f7f7f7f;
struct node{
	long double x;int cur;
	bool operator<(const node&rhs)const{
	  return x<rhs.x;}
};
node ns[nmax];
int a[nmax],b[nmax];
ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	int n=read(),K=read();
	rep(i,1,n) b[i]=read(),a[i]=read();
	double l=0,r=10000,mid,ans,sm;
	while(r-l>eps){
		mid=(r+l)/2;
		rep(i,1,n) ns[i].cur=i,ns[i].x=a[i]*1.0-mid*b[i];
		sort(ns+1,ns+n+1);
		sm=0;rep(i,n-K+1,n) sm+=ns[i].x;
		if(sm>=0) ans=l=mid;
		else r=mid;
	}
	ll ta=0,tb=0;
	rep(i,n-K+1,n) ta+=a[ns[i].cur],tb+=b[ns[i].cur];
	ll tp=gcd(ta,tb);
	printf("%lld/%lld
",ta/tp,tb/tp);
	return 0;
}

1257 背包问题 V3

基准时间限制：3 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

N个物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），从中选出K件物品（K <= N)，使得单位体积的价值最大。

Input

第1行：包括2个数N, K(1 <= K <= N <= 50000)
第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)

Output

输出单位体积的价值（用约分后的分数表示）。

Input示例

Output示例

3/4