ABC 034 D - 食塩水 ( Binary Search )

D: 食塩水 - AtCoder Beginner Contest 034 | AtCoder
If it is possible to make p%, it will also be possible to make p - 1%. With this property, we know that we can try binary search on the percentage. For a fixed percentage x, we can calculate for each liquid how much extra salt will be left, or required to remain that percentage, which we will take K of them and see whether there is still debt in salt.

int K, N;
int W[ MAXN ], P[ MAXN ];;

bool ok( double g ){
    priority_queue< double > pq;
    for( int i = 0; i < N; ++i ){
        pq.push( 1.0 * W[ i ] * P[ i ] / 100 - 1.0 * W[ i ] * g / 100 );
    }
    double res = 0;
    for( int i = 0; i < K; ++i )
        res += pq.top(), pq.pop();
    return res >= 0;
}

void solve(){
    cin >> N >> K;
    for( int i = 0; i < N; ++i )
        cin >> W[ i ] >> P[ i ];
    double lb = 0, rb = 100;
    for( int i = 0; i < 100; ++i ){
        double mid = ( lb + rb ) / 2;
        if( ok( mid ) ) lb = mid;
        else rb = mid;
    }
    cout << lb << "\n";
}