第1行：包括2个数N, K(1 <= K <= N <= 50000) 第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)
输出单位体积的价值（用约分后的分数表示）。
3 2 2 2 5 3 2 1
3/4
一道经典问题，在《挑战程序设计竞赛第2版》143页中有原题，最大化平均值。
刚开始我也是想 按照z=p/w 排序，但是这种贪心有问题的。
想到二分答案。
假设知道答案x
那么我们知到总价值要>=x*k;
Sum(p[i])/Sum(w[i])>=x;
Sum只有K个
那么S
Sum(p[i]>=Sum(w[i】*x);
于是 每次求Sum(p[i]-w[i]*x)>=0;求totx,toty最大
难看的代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 211111
struct node
{
int w,p;
double c;
}a[N];
int cmp(node a,node b)
{
return a.c>b.c;
}
int n,k;
ll gcd(ll x,ll y)
{
if (y==0) return x;
return gcd(y,x%y);
}
ll ax,ay;
int pan(double xx)
{
ll x,y;
x=y=0;
for (int i=1;i<=n;i++)
a[i].c=1.0*a[i].p-xx*a[i].w;
sort(a+1,a+n+1,cmp);
double sum=0;
for (int i=1;i<=k;i++)
{
sum+=a[i].c;
x+=a[i].p;
y+=a[i].w;
}
if (sum>=0)
{
ax=x;
ay=y;
return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].p);
double l=0,r=5000000000.0;
for (int _=1;_<=100;_++)
{
double mid=(l+r)*0.5;
if (pan(mid)) l=mid;
else r=mid;
}
cout<<ax/gcd(ax,ay)<<"/"<<ay/gcd(ax,ay)<<endl;
return 0;
}
PS:做过的类型题，却忘记怎么解决.根本做了没有用。
的确要反思自己的学习方式了
原文：http://www.cnblogs.com/blankvoid/p/4970544.html