NC15446 题解

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;
}