Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Pair implements Comparable<Pair> {
- int a;
- int b;
- Pair(int a, int b) {
- this.a = a;
- this.b = b;
- }
- @Override
- public int compareTo(Pair o) {
- if (ans * b - a - (ans * o.b - o.a) < 0) return -1;
- else return 1;
- }
- }
- double ans;
- void solve() throws IOException {
- int n = readInt();
- int k = readInt();
- int[] a = new int[n];
- int[] b = new int[n];
- double l = 0;
- double r = 1e10;
- for (int i = 0; i < n; i++) {
- a[i] = readInt();
- b[i] = readInt();
- }
- TreeSet<Pair> next = new TreeSet<>();
- int c = 200;
- while (c-->0){
- ans = (l + r) / 2;
- next.clear();
- for (int i = 0; i < n; i++) {
- next.add(new Pair(a[i], b[i]));
- }
- double ch = 0;
- double zn = 0;
- for (int i = 0; i < k; i++) {
- Pair next_ = next.pollFirst();
- ch += next_.a;
- zn += next_.b;
- }
- if (ch / zn >= ans) {
- l = ans;
- } else {
- r = ans;
- }
- }
- out.println(ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement