定义

• 有n个物品，每个物品有价值和消耗，从其中拿k个，希望使得 ∑价值/∑消耗 最大

方法

• 设最优解X=∑v/∑c，对式子做变形有∑v-X∑c=0，再变形有∑(v-Xc)=0
• 易发现这是一个单调式子，故考虑使用二分
• 二分X，每次计算当前X下的(v-Xc)，取前k个求∑(v-Xc)，如果小于0则没有意义，如果大于0，则说明可行，存下来答案

注意

• 如果变为实数域上二分循环条件就变为

while(r-l>eps){……} 

• 同样的，二分对左右界的更新变为

l=mid
r=mid

例题-AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct{int w,v;long long tp;}WP;
WP a[505050];
int n,k;
bool cmp(WP a,WP b){
    return a.tp>b.tp;
}
long long judge(long long x){
    for(int i=0;i<n;i++){
        a[i].tp=a[i].v-x*a[i].w;
    }
    sort(a,a+n,cmp);
    long long sum=0,sa=0,sb=0;
    for(int i=0;i<k;i++){
        sum+=a[i].tp;
        sa+=a[i].v;
        sb+=a[i].w;
    }
    if(sum<0)return -1;
    else return sa/sb;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i].w,&a[i].v);
        }
        long long l=0,r=1e12+7,ans=0;
        while(l<=r){
            long long mid=(l+r)>>1;
            int tmp=judge(mid);
            if(tmp==-1)r=mid-1;
            else {
                l=mid+1;
                ans=tmp;
            }
        }
        printf("%lld\n",ans);
    }
}