Submission #935434

---

Source Code Expand

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  class Node {
    int w;
    int p;

    @Override
    public String toString() {
      return "{w = " + w + ", p = " + p + "}";
    }
  }

  void run() {
    int n = ni();
    int k = ni();
    int[] w = new int[n];
    int[] p = new int[n];
    Node[] wp = new Node[n];
    for (int i = 0; i < n; ++i) {
      w[i] = ni();
      p[i] = ni();
      Node node = new Node();
      node.w = w[i];
      node.p = p[i];
      wp[i] = node;
    }
    double left = 0;
    double right = 100;
    while ((right - left) > 1e-9) {
      final double mid = (left + right) / 2.0;
      Arrays.sort(wp, new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
          double a = o1.w * (o1.p - mid) / 100.0;
          double b = o2.w * (o2.p - mid) / 100.0;
          return Double.compare(b, a);
        }
      });
//      debug(wp);
      long sum = 0;
      double sio = 0;
      for (int i = 0; i < k; ++i) {
        sio += wp[i].w * (wp[i].p / 100.0);
        sum += wp[i].w;
      }
      double per = sio / sum * 100;
      debug(sio, sum, per);
      if (per < mid) {
        right = mid;
      } else {
        left = mid;
      }
    }
    System.out.println((left + right) / 2.0);
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  /*
  class BIT<T> {
    int n;
    ArrayList<T> bit;
    BiFunction<T, T, T> bif;

    BIT(int n, BiFunction<T, T, T> bif, T defaultValue) {
      this.n = n;
      bit = new ArrayList<>(n + 1);
      for (int i = 0; i < n + 1; ++i) {
        bit.add(defaultValue);
      }
      this.bif = bif;
    }

    void update(int i, T v) {
      for (int x = i; x <= n; x += x & -x) {
        bit.set(x, bif.apply(bit.get(x), v));
      }
    }

    T reduce(int i, T defaultValue) {
      T ret = defaultValue;
      for (int x = i; x > 0; x -= x & -x) {
        ret = bif.apply(ret, bit.get(x));
      }
      return ret;
    }
  }
*/
  long MOD = 1_000_000_007;

  long pow(long a, long r) {
    long sum = 1;
    while (r > 0) {
      if ((r & 1) == 1) {
        sum *= a;
        sum %= MOD;
      }
      a *= a;
      a %= MOD;
      r >>= 1;
    }
    return sum;
  }

  long C(int n, int r) {
    long sum = 1;
    for (int i = n; 0 < i; --i) {
      sum *= i;
      sum %= MOD;
    }
    long s = 1;
    for (int i = r; 0 < i; --i) {
      s *= i;
      s %= MOD;
    }
    sum *= pow(s, MOD - 2);
    sum %= MOD;

    long t = 1;
    for (int i = n - r; 0 < i; --i) {
      t *= i;
      t %= MOD;
    }
    sum *= pow(t, MOD - 2);
    sum %= MOD;

    return sum;
  }
}

Submission Info

Judge Result