牛客网2018年东北农业大学春季校赛 I---wyh的物品 0/1分数规划

链接：https://ac.nowcoder.com/acm/contest/93/I?&headNav=www
来源：牛客网

时间限制：C/C++ 5秒，其他语言10秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值
输出描述:
对于每组测试数据，输出对应答案，结果保留两位小数

示例1

输入

1
3 2
2 2
5 3
2 1

输出

0.75

说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的

思路

​ 01分数规划的板子。。。。。。

​ 简单分析一下，我们可以将本题抽象为
$$求式子\frac{{\sum }_{i=1}^n{a}_i\ast x_i}{{\sum }_{i=1}^n{b}_i\ast x_i}=ans的最大值，其中x_i为若选择第i个物品为1，否则为0$$
我们猜测ans的值为L,可以把式子变形为
$$是否存在一组解\{x_1,x_2...,x_n\}可以使得\sum _{i=1}^n(a_i-L\ast b_i)\ast x_i>=0$$

现在很明了了，我们只需要对答案进行二分，令L=mid，每次check进行中间值 $(a_i-L\ast b_i)$从大到小排序，取前k个就OK了

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define eps 1e-7
int n,k;
long long a[100005],b[100005];
double tt[100005];
bool cmp(double a,double b){
   
    return a>b;
}
bool check(double x){
   
    for(int i=0;i<n;i++){
   
        tt[i]=(double)a[i]-x*(double)b[i];
    }
    sort(tt,tt+n,cmp);
    double sum=0;
    for(int i = 0; i<k;i++){
   
        sum+=tt[i];
    }
    return sum+eps>=0;
}
int main(void){
   
    int t;
    scanf("%d",&t);
    while(t--){
   
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
   
            scanf("%lld%lld",&b[i],&a[i]);
        }
        double left=0,right=0x3f3f3f3f;
        while(left+eps<right){
   
            double mid = (left+right)/2.0;
            if(check(mid)){
   
                left=mid;
            }
            else{
   
                right=mid;
            }
        }
        printf("%.2lf\n",left);
    }
    return 0;
}