wyh的物品

和另一道一样，01分数规划+二分。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double esp=0.00000001;
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        int k;
        int w[101000],v[110000];
         double sum[110000];
        double max1=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
            double l=0.0,r=1000000000.0,mid=0.0;
            for(int i=1;i<=100;i++){//防止double精度造成死循环
                 mid=(l+r)/2.0;
                for(int i=1;i<=n;i++) sum[i]=1.0*v[i]-1.0*mid*w[i];
                sort(sum+1, sum+n+1, greater<double>());
                double total=0.0;
                for(int i=1;i<=k;i++) total+=(1.0*sum[i]);
                if(total>=0.0) l=mid;
                else r=mid;
            }
            printf("%0.2f\n",mid);//注意换行
    }

}