training.java

public static void main(String[] args) {
    Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

    int testCases = s.nextInt();
    int caseNum = 1;
    Training training = new Training();

    while (caseNum <= testCases) {
        int n = s.nextInt();
        int p = s.nextInt();
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = s.nextInt();
        }
        System.out.println(String.format("Case #%d: %d", caseNum, training.calculateMinTrainingTime(scores, p)));
        caseNum++;
    }
}

private int calculateMinTrainingTime(int[] scores, int pickedCount) {
    if (scores == null || scores.length == 0 || pickedCount <= 0) {
        return -1;
    }
    // convert to integer array to sort in descending order
    Integer[] scoresInteger = new Integer[scores.length];
    for (int i = 0; i < scores.length; i++) {
        scoresInteger[i] = new Integer(scores[i]);
    }
    // really no easier way to sort in descending order, bummer
    Arrays.sort(scoresInteger, Collections.reverseOrder());

    // build up a prefix array, inclusive
    int[] prefixSum = new int[scores.length];
    int sum = 0;

    for (int i = 0; i < scoresInteger.length; i++) {
        sum += scoresInteger[i];
        prefixSum[i] = sum;
    }

    int minTrainingTime = Integer.MAX_VALUE;

    for (int i = 0; i + pickedCount <= scoresInteger.length; i++) {
        // assuming we pick the index i to be the highest score with following elements
        int expectedTrainingTime = scoresInteger[i] * pickedCount;
        int existingTrainingTime = prefixSum[i + pickedCount - 1] - prefixSum[i] + scoresInteger[i];
        int extraTrainingTime = expectedTrainingTime - existingTrainingTime;
        minTrainingTime = Math.min(minTrainingTime, extraTrainingTime);
    }

    return minTrainingTime;
}