51nod_1257_背包问题V3

题目大意

​ 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示例

1
2
3
4
3 2
2 2
5 3
2 1

Output示例

1
3/4

题解:

​ 简单的分数规划(虽然我也不知道分数规划是什么奇怪的东西)

​ 大概就是二分答案之类的操作。

​ 贝爷看到这题的时候:有什么比较好的二分分数的方法么?

​ 然鹅事实上并不用二分分数,用实数进行二分之后最后算一波答案就可以了。

​ 因为判定过程中用到了排序所以给出的代码时间复杂度是两只log的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int n,k,xx,yy,zz;
double l,r,m;
struct lsg{int x,y;double sum;}a[1000000];
int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int kk=1,k=0;if (c=='-')kk=-1,c=getchar();
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}bool cmp(lsg x,lsg y){return x.sum>y.sum;}
double pd(double x){
for (int i=1;i<=n;i++)a[i].sum=a[i].x-x*a[i].y;
sort(a+1,a+1+n,cmp);double ans=0;for (int i=1;i<=k;i++)ans+=a[i].sum;
return ans;
}int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main(){
n=read();k=read();for (int i=1;i<=n;i++){
a[i].y=read();a[i].x=read();r=max(r,1.0*a[i].x/a[i].y);
}while (l+1e-8<r){
double m=(l+r)/2;if (pd(m)>=0)l=m;else r=m;
}pd(l);for (int i=1;i<=k;i++)xx+=a[i].x,yy+=a[i].y;
zz=gcd(xx,yy);xx/=zz;yy/=zz;cout<<xx<<'/'<<yy<<endl;
}

(by the way:混凝土数学里似乎有一种绝妙的枚举所有有理分数的操作

分享到