CF1859C 题解

思路

我们实际上发现它计算的就是 \(p_i \cdot i\) 的和再减去一个 \(p_i \cdot i\) 中的最大值。

那我们可以枚举这个最大值 \(p_x \cdot x\)，这个值就是最后和中需要删除的数值。

这里我们可以使用贪心。

我们可以从 \(n \sim 1\) 枚举除 \(p_i\) 的每个数字需要配的数字。

当然，越大的数字 \(p_i\)，配的数字 \(i\) 也应该越大，这样才能使和最大。

我们还要注意选最大的 \(p_i \cdot i\) 一定不能超过 \(p_x \cdot x\)。

加一些剪枝就过了。

最坏时间复杂度：\(O(n^4)\)，最多需要跑 \(4.6 \times 10^9\) 次。

因为时间限制有 \(3\) 秒（不要质疑 CF 的机子），所以放心跑。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 260;

bool vis[N];

void solve() {
	int n, ans = 0;
	cin >> n;
	int res = 0;
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= n; b++) {
			int maxx = a * b, ans = 0;
			if (maxx < n) continue;
			if (a * b * n <= res) continue;
			memset(vis, 0, sizeof(int) * (n + 10));
			vis[b] = true;
			for (int i = n; i >= 1; i--) {
				if (i == a) continue;
				int maxp = min(n, maxx / i);
				while (maxp >= 1 && vis[maxp]) maxp--;
				if (maxp == 0) {
					ans = -0x3f3f3f3f;
					break;
				}
				vis[maxp] = true;
				ans += maxp * i;
			}
//			cout << a << ' ' << b << ' ' << ans << endl;
			res = max(res, ans);
		}
	}
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	return 0; 
}