小咪买东西

原题链接

典型的二分答案，01规划。

那么我们只需要二分x求出最大的x即可，因此我们只需求出所有v-x*c的值并把最大的k个求和保证sum>=0即可。

主要代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
int a[N],b[N],n,k,c[N];
bool check(int x){
    ll sum=0;
    for (int i=0;i<n;i++)
        c[i]=b[i]-x*a[i];
    sort(c,c+n);
    for (int i=n-1;i>=n-k;i--) sum+=ll(c[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]>>b[i];
        int left=0,right=1e4+5;
        while (left+1<right){
            int mid=left+(right-left>>1);
            if (check(mid)) left=mid;
            else right=mid;
        }
        printf("%d\n",left);
    }
    return 0;
}

ps：sum要保证longlong型，因为1e4*1e4*1e4（x取1e4，c取1e4，1e4个相加）超出了int