小咪买东西

求单位最值，考虑01分数规划；
x=∑a[i]/∑b[i]，所以∑a[i]-x*∑b[i]=0 ∑ ( a[i] - x * b[i] )
枚举x，取k个物品，看代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double esp=0.000001;
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        int k;
        double w[101000],v[110000],sum[110000];
        double max1=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
            double l=0,r=1000000,mid;
            while(abs(r-l)>esp)
            {
                 mid=(l+r)/2.0;
                for(int i=1;i<=n;i++) sum[i]=v[i]-mid*w[i];//算出每个物品的比值，如果小于0，则比值<mid，大于等于0，则>=mid
                sort(sum+1,sum+1+n);//排序，选择比值较大的
                double total=0;
                for(int i=n;i>n-k;i--) total+=sum[i];//取k个
                if(total>=0.0) l=mid;//如果total>=0，说明mid可以取到
                else r=mid;
            }
          cout<<int(mid)<<endl;
    }

}