CF985C 题解

建议升绿

这道题是一道贪心。很容易想到，我们你需要先进行一次排序，然后再进行一些操作。

首先我们可以排除无解的情况，当第 \(n\) 短的木板的长度与最短的木板的长度之差 \(> l\) 时，不可能有任何一种符合题意的方案。这个很好证，有兴趣的朋友可以自己证一下。

然后我们考虑如何制定一个合理的贪心计划。首先我们可以尝试确定一个最大的桶大小，这对后面的操作有很大的帮助。很显然，最大的桶大小就是与最短木板长度的差 \(\leq l\) 的最大的一块木板。然后我们可以优先构造大小为最大大小的木桶，设此时找到的代表着最大溶剂的木板的下表为 \(p\) ，我们应该尝试让长度 \(\geq a_p\) （\(a\) 数组为木板长度的数组）的木板 \(p\) 进行配对，同时更新最大长度的下标（即 p -= 1）。

然后我们可以简单的统计一下剩下的桶的大小，求和即可。

AC Code ：

#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

int n, k, t, ans, a[100009];

signed main() {
	cin >> n >> k >> t;
	for (int i = 1; i <= n * k; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n * k + 1);
	if (a[n] - a[1] > t) {
		cout << 0;
		return 0;
	}
	int p = n * k, cnt = 0;
	while (a[p] - a[1] > t) {
		p -= 1;
	}
	for (int i = n * k, j = p; i >= p + k; i -= (k - 1), j -= 1, cnt += 1) {
		ans += a[j];
	}
	for (int i = 1; i <= p - cnt; i += k) {
		ans += a[i];
	}
	cout << ans;
}