POJ-2976-Dropping tests

题目描述：

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

image

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

image

However, if you drop the third test, your cumulative average becomes

image

输入：

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.

输出：

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

输入示例：

1
2
3
4
5
6
7
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

输出示例：

1
2
83
100

提示：

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题目大意：

有N个考试，每个考试有ai和bi两个值，最后成绩由上面的公式求得。幸运的是，可以放弃K个科目，求最大化最后的成绩。(输出乘100后四舍五入的结果)

思路：

由题意可知当，当n-k个科目组成最优解时，再增加别的科目，解一定不如原来的解，放弃掉k个科目是最好的方案。

于是，题目就变成了最小化平均值的问题，另外在注意下取整时的四舍五入就好了。

最小化平均值:

有n个物品的重量和价值分别为wi和vi，从中选择k个物品使得单位重量的价值最大。

对于这个问题，我们可以用二分搜索解决，先来看看判断条件：
设最大值为x，则需要满足 ∑vi / ∑wi >=x，把不等式进行变形，就得到了 ∑ ( vi - x wi )>=0，于是判断就成了，对 vi-xwi 的值进行排序之后贪心进行选择，判断前n-k个的和是否不小于0。判断的复杂度是O（nlogn）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * @Date: 2019-09-28 16:40:15
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-29 18:14:27
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int MAXN = 1000+10;
int n,k;
struct node{
    int a,b;
}num[MAXN];

double f[MAXN];


bool check(double x){
    for(int i = 0; i < n; i++) f[i] = num[i].a - x*num[i].b;
    sort(f,f+n);
    double sum = 0;
    for(int i = 0; i <n-k; i++) sum += f[n-1-i];
    return sum >= 0;
}

int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&k)!= EOF && n+k){
        for(int i = 0; i < n; i++){
            scanf("%d",&num[i].a);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&num[i].b);
        }
        double l = 0, r = 1e9;
        for(int i = 0; i < 100; i++){
            double mid = (l+r)/2;
            if(check(mid)) l = mid;
            else r = mid;
        }
 
		printf("%d\\n", int(l*100+0.5));

        // int ans = 100 * (l+0.005);
		// printf("%d\\n", ans);
    }

}