题目链接
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;
}
