ABC034 D - 食塩水

やり直し

D - 食塩水

解説

平均を最大化する問題->二分探索

wiグラムの濃度pi%の食塩水をk個混ぜた時の濃度は、

これがp以上となる時は

を満たす。

変形すると、

濃度がp以上の食塩水を作れるかどうかは、 の値が大きい容器からK個選んで0以上となっていれば作れるとわかる。

pの値で二分探索すればOK。

今回pは実数なので、探索する区間が十分小さくなるようにforで回せばOK。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
// 平均最大化
int N, K;
double w[1000], p[1000];
bool calc(double pp) {
  vector<double> v;
  FOR(i,0,N) {
    v.push_back((p[i] - pp) * w[i]);
  }
  sort(v.rbegin(), v.rend());
  double m = 0;
  FOR(i,0,K) m += v[i];
  return m >= 0; 
}
int main()
{
  cin >> N >> K;
  FOR(i,0,N) cin >> w[i] >> p[i];
  double l = -1, r = 1000;
  FOR(i,0,100) {
    double m = (l + r) * 0.5;
    if(calc(m)) l = m;
    else r = m;
  }
  printf("%.10lf\n",l);
  return 0;
}

平均最大化の問題だと気がつかなかった