Poj 2976: Dropping tests

poj2976.md

Poj 2976: Dropping tests

題目

分析

平均最大化 => 二分搜

以下所有的 average 都是指 sum(a) / sum(b) （還未乘以 100）

正負相關性判定

bool C(average) = 放棄 K 個測驗後，可否使平均 >= average

而 C(average) 表是

1 1 1 1 0 0 0

這種形式，而我們的目標是尋找最後一個 1 在哪

---

至於如何實作 C(average) 呢？設 S 是解的集合，即 Courses 的子集， 觀察

sum(a[i] for i in S) / sum(b[i] for i in S) >= A

移項後得

sum(a[i] for i in S) - A * sum(b[i] for i in S) >= 0

所以我們只需計算 a - A * b 最大的 N - K 個 Courses，看他們的平均是否 >= average

上下界判定

上下界明顯分別為 1.0, 0.0 ，即全部答對與全部答錯， 這時不管要放棄幾科，平均都仍是 1.0, 0.0 。

二分搜次數

解的範圍是 double 區間，且是 [lb, ub]，為防止浮點數誤差，改採進行定量次數的二分搜。

二分搜進行 20 次，精度就變為 (1.0 - 0.0) / (2 ^ 20)（應該是這樣算沒錯吧？）， 即使最後答案乘以 100，精度仍高於題目所說的 1e-3。

其它

四捨五入，round 涵式似乎在 c++11 才有，所以只好改用 floor(x + 0.5)

AC Code

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

int N, K;
double A;

struct Course {
	int a, b;
	bool operator > (const Course& c) const {
		return a - A * b > c.a - A * c.b;
	}
};

Course courses[1000];

bool C(double average) {
	A = average;

	sort(courses, courses + N, greater<Course>());

	double sum_a = 0.0, sum_b = 0.0;
	for (int i = 0; i < N - K; i++) {
		sum_a += courses[i].a;
		sum_b += courses[i].b;
	}

	return sum_a / sum_b >= average;
}

int solve() {
	// [lb, ub]
	double lb = 0;
	double ub = 1;

	for (int i = 0; i < 20; i++) {
		double mid = (lb + ub) / 2;
		if (C(mid)) lb = mid;
		else ub = mid;
	}

	// return round(lb * 100.0)
	return floor(lb * 100.0 + 0.5);
}

int main() {
	while (scanf("%d %d", &N, &K) != EOF) {
		if (N == 0 && K == 0) break;

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

		printf("%d\n", solve());
	}
	return 0;
}