[POJ2976][分数规划]Dropping tests[水题]

[题目大意]

你考了N次试，第i次考试有bi道题，你通过了ai道。现在选择(N-K)次考试，使得总通过率最高。（总通过率 = 选择的考试的总通过数/选择的考试的总题目数）

[分析]

第一反应是贪心，可惜贪心不对，样例给的很明显了。想一想，利用分数规划，二分答案，每次判断答案是否可行，这时候就可以用贪心了。

注意精度要卡小一点，以前卡1e-4就挂了，卡到1e-7就过了……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

//Global Variables & Definitions
int N, K;
int a[1010], b[1010];
double w[1010];
//End Global Variables & Definitions

//Main Structure
const double eps = 1e-7;

double solve() {
	for(int i = 0;i < N;++i) scanf("%d", &a[i]);
	for(int i = 0;i < N;++i) scanf("%d", &b[i]);

	double L = 0.0, R = 1.1;
	while(R - L >= eps) {
		double mid = (L + R) / 2.;

		for(int i = 0;i < N;++i) w[i] = a[i] - b[i] * mid;
		sort(w, w + N);

		double ans = 0.;
		for(int i = K;i < N;++i) ans += w[i];

		if(ans > 0.0) 
			L = mid;
		else
		    R = mid;
	}

	return (L + R) / 2.;
}

int main() {
	while(scanf("%d%d", &N, &K) && N) printf("%.0f\n", solve() * 100);
	return 0;
}