NC15446
的物品 [
](https://ac.nowcoder.com/acm/problem/15446)
题目描述
学长现在手里有
个物品,这
个物品的重量和价值都告诉你,然后现在让你从中选取
个,问你在所有可能选取的方案中,最大的单位价值为多少(单位价值为选取的
个物品的总价值和总重量的比值)。
输入描述
输入第一行一个整数 。
接下来有 组测试数据,对于每组测试数据,第一行输入两个数
和
。
接下来有 行,每行两个是
和
,代表这个物品的重量和价值。
输出描述
对于每组测试数据,输出对应答案,结果保留两位小数。
示例1
输入
1
3 2
2 2
5 3
2 1
输出
0.75
说明
对于样例来说,我们选择第一个物品和第三个物品,达到最优目的。
分析
设使得单位价值最大的 个物品的索引为
。当二分得到一个答案
,假设
小于最大单位价值或恰好为最大单位价值,那么有
,即
,若不存在
的方案,即
,说明
大于最大值,右边界减小,否则
合法。
代码
#include<iostream> #include<algorithm> #include<cstdio> #define N 100003 #define eps 1e-6 using namespace std; int value[N],weight[N]; double p[N]; int n,k; bool check(double x) { int i; for(i=1;i<=n;i++) p[i]=value[i]-x*weight[i]; sort(p+1,p+1+n,greater<double>()); double res=0; //前k大的value[i]-x*wight[i]之和即为最大值 for(i=1;i<=k;i++) res+=p[i]; return res>=0;//若非负则x合法 } int main() { int _; for(cin>>_;_;_--) { scanf("%d%d",&n,&k); int i; for(i=1;i<=n;i++) scanf("%d%d",weight+i,value+i); double l=0,r=1e9; double ans; //二分 while(r-l>=eps) { double mid=(l+r)/2; if(check(mid)) { ans=l;//mid合法,更新答案 l=mid; } else r=mid; } printf("%.2lf\n",ans); } return 0; }