Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.30 KB | None | 0 0
  1. class Pair implements Comparable<Pair> {
  2.         int a;
  3.         int b;
  4.  
  5.         Pair(int a, int b) {
  6.             this.a = a;
  7.             this.b = b;
  8.         }
  9.  
  10.         @Override
  11.         public int compareTo(Pair o) {
  12.             if (ans * b - a - (ans * o.b - o.a) < 0) return -1;
  13.             else return 1;
  14.         }
  15.     }
  16.  
  17.     double ans;
  18.  
  19.     void solve() throws IOException {
  20.         int n = readInt();
  21.         int k = readInt();
  22.         int[] a = new int[n];
  23.         int[] b = new int[n];
  24.         double l = 0;
  25.         double r = 1e10;
  26.         for (int i = 0; i < n; i++) {
  27.             a[i] = readInt();
  28.             b[i] = readInt();
  29.         }
  30.         TreeSet<Pair> next = new TreeSet<>();
  31.        int c = 200;
  32.        while (c-->0){  
  33.             ans = (l + r) / 2;
  34.             next.clear();
  35.             for (int i = 0; i < n; i++) {
  36.                 next.add(new Pair(a[i], b[i]));
  37.             }
  38.             double ch = 0;
  39.             double zn = 0;
  40.             for (int i = 0; i < k; i++) {
  41.                 Pair next_ = next.pollFirst();
  42.                 ch += next_.a;
  43.                 zn += next_.b;
  44.             }
  45.             if (ch / zn >= ans) {
  46.                 l = ans;
  47.             } else {
  48.                 r = ans;
  49.             }
  50.         }
  51.         out.println(ans);
  52.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement