POJ 3111: K Best

概要

n個の宝石があって，k個を残して売り払いたい．その時，残したk個の宝石の単位重さあたりの評価値を最大化したい．

解法

蟻本そのままで二分探索．謎WA連発の末，探索終えた後にもう一回答えを計算したほうがいいという結論に至る．
繰り返し回数が結構シビアかもしれない．

int n, k;
int v[100010], w[100010];

pair<double, int> y[100010];
bool C(double x){
    for(int i = 0; i < n; ++i) y[i] = make_pair(v[i] - w[i] * x, i + 1);
    sort(y, y + n);
    double sum = 0;
    for(int i = 0; i < k; ++i){
        sum += y[n-i-1].first;
    }
    return sum >= 0;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &v[i], &w[i]);
    }
    double lb = 0, ub = 1e8;
    for(int i = 0; i < 50; ++i){
        double mid = (lb + ub) / 2;
        if(C(mid)){
            lb = mid;
        }
        else{
            ub = mid;
        }
    }
    C(lb);
    for(int i = 0; i < k; ++i)
        printf("%d%c", y[n-i-1].second, i == k - 1 ? '\n': ' ');

    return 0;
}