poj 3111 K Best 最大化平均值 二分思想

题目链接：

http://poj.org/problem?id=3111

思路：

• 挑战程序竞赛书上讲的很好，下面的解释也基本来源于此书
• 设定条件C(x):=可以选择使得单位重量的价值不小于x
• 如何判定C(x)是否可行
• 假设选了某个物品的集合是S，那么单位重量的价值是：$$ \sum\limits_{i \in S} {v_i } /\sum\limits_{i \in S} {w_i } $$
• 因此就变成了判断是否存在S满足下面的条件：$$ \sum\limits_{i \in S} {v_i } /\sum\limits_{i \in S} {w_i } \ge x $$
• 把这个不等式变形就得到：$$ \sum\limits_{i \in S} {(v_i - x + w_i )} \ge 0 $$
• 因此可以对\((v_i-x+w_i)\)的值进行排序贪心地进行选取，因此就变成了,满足条件的前k大项。

代码：

#include <iostream>

#include <algorithm>

#include <stdio.h>

using namespace std;

const int maxn = 100005;

const int INF = 1000006;

struct node {

    int v,w,id;

    double y;

    bool operator < (const node& x) const {

        return y>x.y;

    }

} jew[maxn];

int n,k;

bool check(double x) {

    for(int i=1;i<=n;++i) jew[i].y=jew[i].v-jew[i].w*x;

    sort(jew+1,jew+1+n);

    double sum=0;

    for(int i=1;i<=k;++i) sum+=jew[i].y;

    return sum>=0;

}

int main() {

    scanf("%d %d",&n,&k);

    for(int i=1;i<=n;++i) {

        scanf("%d %d",&jew[i].v,&jew[i].w);

        jew[i].id=i;

    }

    double l=0,r=INF;

    for(int i=0;i<100;++i) {

        double mid = (l+r)/2;

        if(check(mid)) l=mid;

        else r=mid;

    }

    for(int i=1;i<=k;++i) {

        if(i==1) printf("%d",jew[i].id);

        else printf(" %d",jew[i].id);

    }

    printf("\n");

    return 0;

}