(POJ) 3111 K. Best [平均最大值]

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

這是「平均最大化」的題目。

我先把題目想成「求出最大的平均值S」。

若平均值=S，則代表說 ( v[1] + v[2] + v[3] + .... + v[k] ) / (w[1] + w[2] + w[3] + ..... + w[k] ) >=S ，則此S具有單調性，那我們可以二分搜 v[x] - S * w[x]  (移項試試看)，就okay了。

O (n lg n)

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100003;

double v[MAX_N];
double w[MAX_N];
double num[MAX_N];
int n,k;


double get_ans(double i) {
    for (int x=0;n>x;x++) num[x] = v[x] - i * w[x];
    sort(num,num+n);
    double ret=0.0;
    for (int x=n-1;x>=(n-k);x--) ret+=num[x];
    return ret;
}

struct Node {
    int id;
    double val;
} node[MAX_N];

bool operator< (const Node& n1, const Node& n2) {
    return n1.val < n2.val;
}

void print_ans(double i) {
    for (int x=0;n>x;x++) node[x].id=x;
    for (int x=0;n>x;x++) node[x].val = v[x] - i * w[x];
    sort(node,node+n);
    double ret=0.0;
    for (int x=n-1;x>=(n-k);x--) {
        printf("%d",node[x].id+1);
        if (x!=n-k) printf(" ");
    }
    puts("");
}

int main () {
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int x=0;n>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            v[x]=i;
            w[x]=j;
        }
        //算式>mu --> v[i] - mu*w[i] 二分搜XDDD
        double l=0.0,r=20000000.0;
        while (r-l > 1e-7) {
            double mid=(l+r)/2;
            double ret=get_ans(mid);
            if (ret>=0.0) l=mid;
            else r=mid;
        }
        print_ans(r);
    }
}