二分搜索，最大化平均值 Poj-3111

题目链接:https://vjudge.net/problem/POJ-3111

题目大意就是给你一堆有价值和重量的珠宝，问你如何挑选能够是最终单位珠宝的价值最大。

 

首先我们的思路肯定是贪心，按照它们的单位价值进行排序，取最大的几个。但是这是错误的。在这组数据中贪心就是错误的

k = 2

{w,v} = {2,2} , {5,3} , {2,1}

依照贪心的思想我们肯定会选取 {5，3}和{2，2}这一组，此时的单位价值x = 7/3 = 0.714，但实际情况我们取到了{2，2} + {2，1}

x  = 0.75。故此可以得出贪心的思路是错误的。于是去枚举珠宝单价的可能性，常规的暴力会TLE，于是我们是用二分的思想去枚举将时间复杂度从O(n) 降为log(n)。

 

讲解来自《挑战程序设计竞赛》

设最大的单位价值为x。那么让x成立的条件为 ∑v / ∑w ≥ x 化简可以得到 ∑v / ∑w ≥ x  = > ∑v ≥ x * ∑w = ∑ (x*w)  = > ∑ (v - x * w) ≥  0，所以我们只要让前k个物品都满足这个条件，那么此时的x就是符合条件的，我们再去找更大的就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define lson l m rt << 1
#define rson m+1 r rt << 1|1
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+10;
const int mod = 1000;
ll v[maxn],w[maxn];
ll T,n,k;
inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

struct Node
{
    int v,w,id; //价值，重量，编号
    double y;//排序时候判断是否都满足x
}a[maxn];

bool cmp(Node a,Node b)  //从大到小排序
{
    return a.y > b.y;
}

bool check(double x)
{
    for(int i = 0;i < n;++i)
    {
        a[i].y = a[i].v - a[i].w*x;   //推导出来的公式
    }

    sort(a,a+n,cmp);

    double sum = 0;
    for(int i = 0;i < k;++i)  //如果sum最后大于零表示此时的X合适我们去二分更大的
        sum += a[i].y;

    return sum >= 0;
}

int main()
{
    fast();
    while(scanf("%lld %lld",&n,&k) != EOF)
    {
        for(int i = 0;i < n;++i)
        {
            scanf("%d %d",&a[i].v,&a[i].w);
            a[i].id = i+1;
        }

        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 = 0;i < k;++i)
        {
            if(i == 0)
                printf("%d",a[i].id);
            else
                printf(" %d",a[i].id);
        }
        printf("\n");
    }
	return 0;
}