KBest (POJ 3111)
Similar to Dropping Tests, this is a maximizing average value problem. The solution is:
import java.io.*;
import java.util.*;
class Jewel implements Comparable<Jewel> {
int i;
double v;
double w;
double r = 0.0;
public Jewel(int i, double v, double w) {
this.i = i;
this.v = v;
this.w = w;
}
public int compareTo(Jewel b) {
return (b.r - this.r > 0) ? 1 : -1;
}
}
public class KBest {
private static boolean valid(Jewel[] jewels, double avg, int k) {
for (Jewel j: jewels) j.r = j.v - j.w * avg;
Arrays.sort(jewels);
double sum = 0;
for (int i = 0; i < k; i++) sum += jewels[i].r;
return sum >= 0;
}
private static void solve(Jewel[] jewels, int k) {
double l = 0, u = 1000000.0;
for (int i = 0; i < 50; i++) {
double av = (l + u) / 2;
if (valid(jewels, av, k)) l = av;
else u = av;
}
int[] result = new int[k];
for (int i = 0; i < k; i++) result[i] = jewels[i].i;
Arrays.sort(result);
System.out.printf("%d", result[0]);
for (int i = 1; i < k; i++) System.out.printf(" %d", result[i]);
System.out.println();
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] str = in.readLine().split(" ");
int n = Integer.parseInt(str[0]), k = Integer.parseInt(str[1]);
Jewel[] jewels = new Jewel[n];
for (int i = 1; i <= n; i++) {
str = in.readLine().split(" ");
int v = Integer.parseInt(str[0]), w = Integer.parseInt(str[1]);
jewels[i - 1] = new Jewel(i, v, w);
}
solve(jewels, k);
}
}