题目描述

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

输入描述:

>多组数据。
第一行一个整数T，为数据组数。
接下来有T组数据。
对于每组数据，第一行两个正整数n，k，如题。
接下来n行，每行有两个正整数ci，vi。分别为手办的花费和它对于小咪的价值。

输出描述:

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

备注:

>1≤T≤10
1≤n≤104
1≤k≤n
1≤ci,vi≤104

题解

这应该也是01分数规划的裸题。
https://blog.nowcoder.net/n/c0e93d646a8c4d71a6ef03fcebc6359b
我在这篇博客中详细介绍了怎么用二分去求解01分数规划。
这道题对比那道题只不过是把实数二分换成了整数二分...我也没搞明白为啥他有4颗小星星。
这种题还可以再简单拓展一下，即不给出k让我们求最大值，思想也很简单，就是排完序后原来是把前k个加到一起判是否大于0，现在我们只需要看有没有大于0的即可了~

完整代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int> a[10050];
int n,k;
int c[10050];
bool check(int x){
    for(int i=1;i<=n;++i){
        c[i]=a[i].second-x*a[i].first;
    }
    sort(c+1,c+1+n);
    double sum=0;
    for(int i=n;i>n-k;--i){
        sum+=c[i];
    }
    return sum>=0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i)scanf("%d%d",&a[i].first,&a[i].second);
        int l=0,r=1e4;
        int ans;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
}

(感觉自己这篇题解写的好水嘤嘤嘤)