POJ2976 - Dropping tests - 二分+01分数规划+思维

1.题目描述：

Dropping tests

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11338		Accepted: 3947

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

2.题意概述：

给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i]))   其中a,b都是一一对应的。 x[i]取0,1  并且 ∑x[i] = n - k。

3.解题思路：

 令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了。

4.AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long ll;
#define INF 0x7fffffff
#define maxn 1111
#define eps 1e-15
#define pi acos(-1.0)
#define e 2.718281828459
#define mod (int)1e9 + 7;
double a[maxn], b[maxn], y[maxn];
int n, k;
int judge(double x)
{
	for (int i = 0; i < n; i++)
		y[i] = a[i] - x * b[i];
	sort(y, y + n, greater<double>());
	double sum = 0;
	for (int i = 0; i < n - k; i++)
		sum += y[i];
	return sum >= 0;
}
int main()
{
	/*
	#ifdef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	*/
	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, r = INF, m;
		while (r - l > eps)
		{
			m = l + (r - l) / 2;
			if (judge(m))
				l = m;
			else
				r = m;
		}
		printf("%.0lf\n", m * 100);
	}
	return 0;
}