Poj 3111: K best

poj3111.md

Poj 3111: K best

題目

分析

平均最大化 => 二分搜

雖說題目寫 S = {i[1], i[2], ..., i[k]}，但它所指的是任意選 K 個，而不是選前 K 個

※ 題目所要的輸出即是平均最大化的過程產物。

正負相關性判定

bool C(s) = 選 K 個，可否是 specific value >= s

而 C(s) 表是

1 1 1 1 0 0 0

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

---

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

sum(v[i] for i in S) / sum(w[i] for i in S) >= s = A

移項後得

sum(v[i] for i in S) - A * sum(w[i] for i in S) >= 0

所以我們只需找出 v - A * w 最大的 K 個 Jewels，看他們的 specific value 是否 >= s

上下界判定

下界直接給 0.0，因下界不易判定，所以就給一個足夠小，並使 C(lb) = true 的值。

上界為 sum(v[i] / w[i] | 0 <= i < n)，即 K = N，且 w[i] = 1 for all i

二分搜次數

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

這題須進行 40 次以上二分搜，從題目可判定， 將 specific value 的精度升至個位數，約需 30 次。但個位數應該不夠確定 Jewels 的順序， 所以再多一些，取 40 或 50。

其它

嘗試過將 sort 改成 partial_sort，但會 TLE，仍不確定原因。

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 Jewel {
	int v, w, id;

	bool operator > (const Jewel& j) const {
		return v - A * w > j.v - A * j.w;
	}
};

Jewel jewels[100000];

bool C(double s) {
	A = s;

	sort(jewels, jewels + N, greater<Jewel>());

	double sum_v = 0, sum_w = 0;
	for (int i = 0; i < K; i++) {
		sum_v += jewels[i].v;
		sum_w += jewels[i].w;
	}

	return sum_v / sum_w >= s;
}

void solve() {
	double lb = 0.0;
	double ub = 0.0;
	for (int i = 0; i < N; i++)
		ub += jewels[i].v;

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

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		jewels[i].id = i + 1;
		scanf("%d %d", &jewels[i].v, &jewels[i].w);
	}

	solve();
	for (int i = 0; i < K; i++) {
		if (i != 0)
			printf(" ");
		printf("%d", jewels[i].id);
	}
	puts("");

	return 0;
}