题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1257

题解：不能按照单位价值贪心，不然连样例都过不了

要求的r=sum(x[i]*p[i])/sum(x[i]*w[i])不妨设一个辅助函数

z(l)=sum(x[i]*p[i])-l*sum(x[i]*w[i]),

如果z(l) > 0 即sum(x[i]*p[i])-l*sum(x[i]*w[i])>0-->sum(x[i]*p[i])/sum(x[i]*w[i])>l也就是说存在

比当前更大的l值也就是所要求的最大值r，于是二分一下答案就行了。

#include <iostream>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int M = 5e4 + 10;struct TnT {    int w , p;    double r;}T[M];int n , k;ll fz , fm;bool cmp(TnT x , TnT y) {    return x.r > y.r;}ll gcd(ll a , ll b) {    return (b > 0) ? gcd(b , a % b) : a;}bool check(double l) {    for(int i = 0 ; i < n ; i++) {        T[i].r = 1.0 * T[i].p - 1.0 * T[i].w * l;    }    sort(T , T + n , cmp);    double sum = 0.0;    fz = 0 , fm = 0;    for(int i = 0 ; i < k ; i++) {        fz += T[i].p;        fm += T[i].w;        sum += T[i].r;    }    if(sum >= 0) return true;    return false;}int main() {    cin >> n >> k;    for(int i = 0 ; i < n ; i++) {        cin >> T[i].w >> T[i].p;    }    double l = 0.0 , r = 50000.0;    ll up , down;    for(int i = 0 ; i <= 50 ; i++) {        double mid = (l + r) / 2;        if(check(mid)) {            l = mid;            up = fz , down = fm;        }        else r = mid;    }    ll gg = gcd(up , down);    cout << up / gg << ‘/‘ << down / gg << endl;    return 0;}

51nod 1257 背包问题 V3（这不是背包问题是二分）