小咪买东西（最大化平均值+二分）

链接：https://ac.nowcoder.com/acm/problem/14662
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办，而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。

输入描述:

多组数据。

第一行一个整数T，为数据组数。

接下来有T组数据。

对于每组数据，第一行两个正整数n，k，如题。

接下来n行，每行有两个正整数ci，vi。分别为手办的花费和它对于小咪的价值。

输出描述:

对于每组数据，输出一个数，即能得到的总价值/总花费的最大值。精确至整数。

示例1

输入

复制

输出

复制

备注:

1≤T≤10

1≤n≤104

1≤k≤n

1≤ci,vi≤104

题意：有n个花费和价值为ci、vi的物品，从中挑选k个使总价值/总花费最大,取整数~

题解：不能直接用贪心法：直接按物品的单位价值排序，然后依次取k个最大的，我们要求的最大值是，价值之和/花费之和，而这样做是单位价值最大然后求和，这样求出的结果跟要求的有差别，比如说：取两个物品：

c v 单位价值

暂时没找出来~~~~~

采用二分方法：价值和/重量和>=x ，价值和-重量和*x>=0 ，价值-重量*x>=0 这样可以对 x进行二分，范围最大是10^4（即：10^4*10^4/10^4,物品价值全是最大，花费全是最小，取最大数量个），最小是0（不解释~），然后对k个进行求和，就是求前k个的价值和-重量和*x，然后判断一下，如果大于等于零，就符合~~小于0不符合~~

注意：二分范围通过考虑极限情况来确定~~

上代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 1e6+100;
struct hh{
    int c,v;
}a[MAX];
int b[MAX];
int n,k;
bool cmp(int x,int y){
    return x>y;
}
bool check(int x){
    for (int i = 0; i < n;i++){
        b[i]=a[i].v-x*a[i].c;
    }
    sort(b,b+n,cmp);
    ll sum=0;//注意范围：需要用long long
    for (int i = 0; i < k;i++){//求前k个的价值和-重量和*x
        sum+=b[i];
    }
    return sum>=0;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> n >> k;
        for (int i = 0; i < n;i++){
            cin >> a[i].c >> a[i].v;
        }
        int l=0;
        int r=1e4+10;//注意：二分范围
        int ans=0;
        while(l<=r){//二分
            int mid=(l+r)>>1;
            if(check(mid)){
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        cout << ans << endl;
    }
    return 0;
}