AtCoder Beginner Contest 034 D: 食塩水

問題

abc034.contest.atcoder.jp

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}
template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}
template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  vector<int> W(N), P(N);
  for (int i = 0; i < N; ++i) cin >> W[i] >> P[i];

  double high = 1.0, low = 0.0;
  while (high - low > 0.000000001) {
    double mid = (high + low) / 2.0;
    vector<double> remain(N);
    for (int i = 0; i < N; ++i) remain[i] = (P[i] / 100.0 - mid) * W[i];
    sort(remain.begin(), remain.end());
    double ok = 0.0;
    for (int i = 0; i < K; ++i) ok += remain[N - 1 - i];
    if (ok > 0.0) {
      low = mid;
    } else {
      high = mid;
    }
  }
  printf("%.15f\n", (high + low) * 50.0);
}