Dropping tests（二分搜索）

Dropping tests

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5592		Accepted: 1925

Description

In a certain course, you take n tests. If you get a_i out of b_i 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 .

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 a_i for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

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.

Sample Input

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

Sample Output

83
100

Hint

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).

Source

Stanford Local 2005

       题意：

       给出 N （1 ~ 1000），K （0 ~ 1000000000）代表有 N 个科目的成绩，每个科目成绩都有 a，b 两种成绩，后给出 N 个 a 和 N 个 b 的成绩。现要使 y =  达到最大，当去除 K 个科目的成绩之后，y 最大能取到多大。

 

       思路：

       二分搜索。y =  ，所以

 

              100 * sigema(a) - y * sigema(b)

           = 100 * （a1 + a2 + …… an） - y * （b1 + b2 + …… bn）

           = （100 * a1 - y * b1）+ （100 * a2 - y * b2 ） + …… +（100 * an - y * bn）

           = 0 ；

 

       故枚举 y 后，先求出每个科目对应的 （100 * ai - y * bi） 值，后由大到小排序，取前面的 n - k 个。

       若求和后的值 > 0，说明 y 小了，应该往右边搜，l = mid；

       若求和后的值 < 0，说明 y 大了，应该往左边搜，r = mid；

       若求和后的值 == 0，说明 y 的值刚刚好，但是可能还有更大的值出现，应该寻找最后一个满足条件的，所以应该往右边搜，l = mid。所以区间应该为左闭右开。

   

       为什么要从大到小排序？

       若从小到大排序的话，求和的结果 < 0 将会占大多数，那么二分搜索就不会不断往左边搜，使这个平均值越来越小，而题目要求的是求最大值。那么应该要让求和结果 > 0 占大多数，那么应该由大到小排序才对。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAX = 1005;

using namespace std;

typedef long long ll;

int n, k;
double a[MAX], b[MAX], c[MAX];

int cmp (double i,double j) { return i > j; }

double Sort (double y) {
        for (int i = 0; i < n; ++i)
                c[i] = 100 * a[i] - y * b[i];

        sort (c, c + n, cmp);

        double ny = 0;
        for (int i = 0; i < n - k; ++i)
                ny += c[i];

        return ny;
}

void solve () {
        double l = 0, r = 100 + 1;

        while (r - l > 0.001) {
                double mid = l + (r - l) / 2;
                double ny = Sort(mid);

                if (ny >= 0) l = mid;
                else r = mid;
        }

        printf("%.lf\n",l);
}

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

                solve();

        }

        return 0;
}