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 and , we'd like to pick a subset from them and maximize the the value of

Usually, we will restrict .

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 that let the value above is less than or equal to our guessed value.

Assume our guessed value is , we are going to verify if there is a subset that let

That is:

So given a guessed and fixed count of elements , we can sort and pick the first 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 so we should decrease the guessed , or the guessed 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 , The time cost is proportional to

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);
        }
    }
}