Dropping Tests (POJ 2976)

This is a typical problem to maximize the average value. There is a general solution to this kind of problems.

Say we have series of values $v_i$ and $w_i$, we'd like to pick a subset $S$ from them and maximize the the value of

$$\frac{\sum_{i \in S} v_i}{\sum_{i \in s} w_i}$$

Usually, we will restrict $|S| \ge K$.

There is no direct way to do this, but we can apply binary search method to guess a average value and verify if it is possible to pick such an $S$ that let the value above is less than or equal to our guessed value.

Assume our guessed value is $R$, we are going to verify if there is a subset $S$ that let $$\frac{\sum_{i \in S} v_i}{\sum_{i \in s} w_i} \le R$$

That is:

$$\sum_{i\in S}v_{i} \le R\sum_{i\in s}w_{i} \Rightarrow \sum_{i\in S}v_{i} \le \sum_{i\in s}R\cdot w_{i} \Rightarrow \sum_{i\in S}v_{i}-R\cdot w_{i} \le 0$$

So given a guessed $R$ and fixed count of elements $K$, we can sort $v_i - R\cdot w_i$ and pick the first $K$ values to sum up to check if it is greater than zero. If it is greater than zero, then there won't be other subset that is feasible with $R$ so we should decrease the guessed $R$, or the guessed $R$ is feasible and we try increase it to find the edge between feasible and infeasible. That value will be maximum possible average value. As we need resort the array for every guessed $R$, The time cost is proportional to $O(N\log^2 N)$

Apply this strategy, we have the solution below. Note as for this kind of problems, the result should be decimal and you should be careful with the calucation and search precision:

import java.io.*;
import java.util.*;

public class DroppingTests {
    private static boolean valid(double[][] tests, double m, int k) {
        final double r = m;
        Arrays.sort(tests, new Comparator<double[]>() {
            public int compare(double[] a, double[] b) {
                double res = (a[0] - a[1] * r) - (b[0] - b[1] * r);
                if (res > 0) return 1;
                else if (res < 0) return -1;
                else return 0;
            }
        });
        double sum = 0;
        for (int i = tests.length - 1; i >= k; i--) {
            sum += (tests[i][0] - tests[i][1] * r);
        }
        return sum >= 0;
    }
    private static void solve(double[][] tests, int k) {
        double l = 0, u = 100.0;
        while ((u - l) > 0.0009) {
            double m = (l + u) / 2;
            if (valid(tests, m, k)) l = m;
            else u = m;
        }
        System.out.println((int)Math.round(u));
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt(), K = in.nextInt();
            if (N == 0 && K == 0) return;
            double[][] tests = new double[N][2];
            for (int i = 0; i < N; i++) {
                tests[i][0] = in.nextDouble() * 100.0;
            }
            for (int i = 0; i < N; i++) {
                tests[i][1] = in.nextDouble();
            }
            solve(tests, K);
        }
    }
}