In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be
.
Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.
Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is
. However, if you drop the third test, your cumulative average becomes 
.
.Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is
. However, if you drop the third test, your cumulative average becomes .
Input
The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed
https://github.com/cherryljr/NowCoder/blob/master/POJ-2976%20Dropping%20tests.java
https://github.com/cherryljr/NowCoder/blob/master/POJ-2976%20Dropping%20tests.java
* 题意：有N个考试，每个考试有ai和bi两个值，最后成绩由上面的公式求得。幸运的是，可以放弃K个科目，求最大化最后的成绩。
* 思路：该题实质上就是一个 最大化平均值 的问题
* 最大化平均值：有n个物品的重量和价值分别为 wi 和 vi，从中选择 k 个物品使得单位重量的价值最大。
*
* 那么首先本题需要确定一个贪心策略，来去掉那些对正确率贡献小的考试。
* 那么如何确定某个考试[ai, bi]对总体准确率x的贡献呢？
* ai / bi肯定是不行的，不然例子里的[0,1]会首当其冲被刷掉。
* 因此这里需要使用到 01分数规划 的一个技巧：
* 题目求的是 max(∑a[i] / ∑b[i])，其中a,b都是一一对应的。
* 那么可以转化一下：
* 令 r = ∑a[i] / ∑b[i]，则有 ∑a[i] - ∑b[i] * r = 0；
* 然后我们就可以 二分枚举 r 的值即可。
* 对于每一个 r, 求出每个 a[i] - b[i] * r; 然后排序，去除 k 个最小值。
* 然后相加得到结果 Q(r)，
* 如果 Q(r) > 0 说明 r 的值偏小，因为可能存在 r 使得 Q(r) = 0；
* 如果 Q(r) < 0 说明选取的 r 值过大；
*
* 时间复杂度：O(nlogn)
*
* 类似的问题：
* Maximum Average Subarray II: (最大化平均值)
* https://github.com/cherryljr/LintCode/blob/master/Maximum%20Average%20Subarray%20II.java
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt(), k = sc.nextInt();
if (n == 0 && k == 0) {
break;
}
double[] a = new double[n];
double[] b = new double[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextDouble();
}
for (int i = 0; i < n; i++) {
b[i] = sc.nextDouble();
}
System.out.printf("%.0f\n", 100 * binarySearch(a, b, n, k));
}
}
private static double binarySearch(double[] a, double[] b, int n, int k) {
double min = 0.0, max = 1.0;
while (Math.abs(max - min) > 1e-6) {
double mid = (max + min) / 2;
double[] arr = new double[n];
for (int i = 0; i < n; i++) {
arr[i] = a[i] - mid * b[i];
}
// Greedy, sort the arr and remove the k smallest elements.
Arrays.sort(arr);
double sum = 0;
for (int i = k; i < n; i++) {
sum += arr[i];
}
if (sum < 0) {
max = mid;
} else {
min = mid;
}
}
return min;
}
题目大意就 给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大，题目求的是 max(∑a[i] * x[i] / (b[i] * x[i]))
乍看以为贪心或dp能解决，后来发现贪心策略与当前的总体准确率有关，行不通，于是二分解决。
依然需要确定一个贪心策略，每次贪心地去掉那些对正确率贡献小的考试。如何确定某个考试[a_i, b_i]对总体准确率x的贡献呢？a_i / b_i肯定是不行的，不然例子里的[0,1]会首当其冲被刷掉。在当前准确率为x的情况下，这场考试"额外"对的题目数量是a_i � x * b_i，当然这个值有正有负，恰好可以作为"贡献度"的测量。于是利用这个给考试排个降序，后k个刷掉就行了。
int n, k;double x; // 搜索过程中的正确率struct Test{ int a, b; bool operator < (const Test& other) const { return a - x * b > other.a - x * other.b; // 按照对准确率的贡献从大到小排序 }};Test test[MAX_N];// 判断是否能够获得大于mid的准确率bool C(double mid){ x = mid; sort(test, test + n); double total_a = 0, total_b = 0; for (int i = 0; i < n - k; ++i) // 去掉后k个数计算准确率 { total_a += test[i].a; total_b += test[i].b; } return total_a / total_b > mid;}///////////////////////////SubMain//////////////////////////////////int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif while (cin >> n >> k && (n || k)) { for (int i = 0; i < n; ++i) { cin >> test[i].a; } for (int i = 0; i < n; ++i) { cin >> test[i].b; } double lb = 0; double ub = 1; while (abs(ub - lb) > 1e-4) { double mid = (lb + ub) / 2; if (C(mid)) { lb = mid; // 行，说明mid太小 } else { ub = mid; // 不行，说明mid太大 } } cout << fixed << setprecision(0) << lb * 100 << endl; }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}http://www.tuicool.com/articles/YFjMvu
看解题报告说是 01分数规划搜索，只看懂了解题报告的意思。
题目大意就 给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大，以下 是复制自其它人的博客
题目求的是 max(∑a[i] * x[i] / (b[i] * x[i]))
转：那么可以转化一下。 令r = ∑a[i] * x[i] / (b[i] * x[i]) 则必然∑a[i] * x[i] - ∑b[i] * x[i] * r= 0；（条件1）
并且任意的 ∑a[i] * x[i] - ∑b[i] * x[i] * max(r) <= 0 (条件2，只有当∑a[i] * x[i] / (b[i] * x[i]) = max(r) 条件2中等号才成立)
然后就可以枚举r , 对枚举的r， 求Q(r) = ∑a[i] * x[i] - ∑b[i] * x[i] * r 的最大值， 为什么要求最大值呢？ 因为我们之前知道了条件2，所以当我们枚举到r为max(r)的值时，显然对于所有的情况Q(r)都会小于等于0，并且Q(r)的最大值一定是0.而我们求最大值的目的就是寻找Q(r)=0的可能性，这样就满足了条件1，最后就是枚举使得Q(r)恰好等于0时就找到了max(r)。而如果能Q(r)>0 说明该r值是偏小的，并且可能存在Q(r)=0,而Q(r)<0的话，很明显是r值偏大的，因为max(r)都是使Q(r)最大值为0，说明不可能存在Q(r)=0了。
double does(double num) { for(int i=0;i<n;i++) { t[i]=a[i]-num*b[i]; } sort(t,t+n); double sum=0.0; for(int i=k;i<n;i++) { sum+=t[i]; } return sum; } int main() { while(scanf("%d%d",&n,&k),n||k) { for(int i=0;i<n;i++) { scanf("%lf",&a[i]); } for(int i=0;i<n;i++) { scanf("%lf",&b[i]); } double l=0.0,r=1.0,mid; while(r-l>eps) { mid=(l+r)/2; if(does(mid)>0)l=mid; else r=mid; } printf("%.0f\n",l*100); } return 0; }X. 01分数规划
https://blog.csdn.net/u013486414/article/details/47398771
Dinkelbach算法求01分数规划：
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-7;
const int maxn=1010;
int n,k;
struct node
{
double a,b,d;
}q[maxn];
int cmp(struct node x,struct node y)
{
return x.d<y.d;
}
double Dinkelbach()
{
double L,ans=0;
double x,y;
while(1){
L=ans;
for(int i=0;i<n;i++)
q[i].d=q[i].a-L*q[i].b;
sort(q,q+n,cmp);
x=y=0;
for(int i=k;i<n;i++){
x+=q[i].a;
y+=q[i].b;
}
ans=x/y;
if(fabs(L-ans)<esp) return L;
}
}
int main()
{
while(~scanf("%d %d",&n,&k)){
if(!n&&!k) break;
for(int i=0;i<n;i++)
scanf("%lf",&q[i].a);
for(int i=0;i<n;i++)
scanf("%lf",&q[i].b);
printf("%.0f\n",Dinkelbach()*100);
}
return 0;
}
Read full article from POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》 � 码农场
