题解40 小咪买东西

前言：这是一道01分数规划题，要用二分+验证解决。记枚举元素为x，sum(value)/sum(cost)>=x即满足要求,sum(value)-x*sum(cost)>=0;则sum(value-x *cost)>=0 sum()=>最大的前k项加起来

AC代码&思路:

#include<iostream>
#include<algorithm>
using namespace std;
long long tmpdp[10010];
int n,k;
struct ty
{
    int cost,value;       
}goods[10010];
bool judge(long long x)
{
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        tmpdp[i]=goods[i].value-x*goods[i].cost;//x*goods[i].cost有可能1e8*1e4=1e12，故x用long long;tmpdp[]用logn long 
    }
    sort(tmpdp+1,tmpdp+1+n);//也可sort( , ,greater<int>()),然后直接输出前k项
    for(int i=n;i>=n-k+1;--i)//倒序的前k项，植树原理,n-(n-k+1)+1=k
    {
        ans+=tmpdp[i];
    }
    return ans>=0;//说明x<=结果
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;++i)
        {
            cin>>goods[i].cost>>goods[i].value;
        }
        long long l=0,r=100000000,mid;
        while(l<r)
        {
            mid=(l+r+1)>>1;
            if(judge(mid)) {l=mid;}//相当于找<=结果的最后一项
            else {r=mid-1;}
        }
        cout<<l<<'\n';
    }
    return 0;
}