Codeforces Round 924 (Div. 2) D. Lonely Mountain Dungeons（推式子，思维，差分，前缀和）

题目链接

Codeforces Round 924 (Div. 2) D. Lonely Mountain Dungeons

思路

令 f ( n , m ) f(n,m) f(n,m)是将 n n n个同种族的人放到 m m m个队伍中可以获得的贡献。

因为同一个队伍中的人不能互相产生贡献，所以尽可能平均分配是最优的。

令 p = ⌊ n m ⌋ p = \left \lfloor \frac{n}{m} \right \rfloor p=⌊mn​⌋， q = n % m q = n \% m q=n%m。那么有 m − q m-q m−q个队伍中有 p p p个人，有 q q q个队伍中有 p + 1 p+1 p+1个人。

则 f ( n , m ) f(n,m) f(n,m)的值为：

前 q q q个： ( p + 1 ) × ( m − p − 1 ) + ( p + 1 ) × ( m − 2 p − 2 ) + . . . + ( p + 1 ) × ( m − q p − q ) (p+1) \times (m - p - 1) + (p+1) \times (m - 2p-2) +...+(p+1) \times (m - qp-q) (p+1)×(m−p−1)+(p+1)×(m−2p−2)+...+(p+1)×(m−qp−q)。

令 Q = ( p + 1 ) × q Q = (p+1) \times q Q=(p+1)×q，则后 m − q m-q m−q个： p × ( m − Q − p ) + p × ( m − Q − 2 p ) + . . . + p × ( m − Q − ( m − q ) p ) p \times (m - Q - p) + p \times (m - Q - 2p) +...+ p \times (m - Q - (m - q)p) p×(m−Q−p)+p×(m−Q−2p)+...+p×(m−Q−(m−q)p)。

根据等差数列求和公式，可以一步得出 f ( n , m ) f(n,m) f(n,m)的值。

因为所有测试用例的 c 1 + c 2 + . . . + c n c_{1}+c_{2}+...+c_{n} c1​+c2​+...+cn​的和不会超过 2 e 5 2e5 2e5，因此我们可以直接枚举种族和队伍个数进行计算，最后差分前缀和就可以了。

时间复杂度： O ( O( O(能过 ) ) )

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, b, x;
int c[N], dp[N];
int func(int n, int m)
{	//计算n个人分到m个队伍可以增加的最多的b单位兵力
	int p = n / m;
	int q = n % m;
	int ans = 0;
	if (m - q > 0)
	{
		ans = (p + 1) * (n * q - q * (q + 1) * (p + 1) / 2);
	}
	else ans = (p + 1) * (n * (q - 1) - (q - 1) * q * (p + 1) / 2);

	int Q = (p + 1) * q;
	if (m - q > 0)
		ans += p * ((n - Q) * (m - q - 1) - (m - q - 1) * (m - q) * p / 2);
	return ans;
}
void solve()
{
	cin >> n >> b >> x;
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < c[i]; j++)
		{
			int acc = func(c[i], j) * b;
			dp[j] += acc;
			dp[j + 1] -= acc;
		}
		int acc = func(c[i], c[i]) * b;
		dp[c[i]] += acc;
	}
	int maxx = *max_element(c + 1, c + 1 + n);
	int ans = 0;
	for (int i = 1; i <= maxx; i++)
	{
		dp[i] += dp[i - 1];
		ans = max(ans, dp[i] - (i - 1) * x);
	}
	for (int i = 1; i <= maxx + 1; i++)
		dp[i] = 0;
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}