作者：美多小涛_584 | 来源：互联网 | 2024-12-23 21:51
引言：本文将详细探讨2019年Nitacm校赛D题——雷顿女士与分队（高级版），旨在帮助读者理解并掌握该问题的解法。
题目链接：点击这里
题目描述：
给定n个人，需要将他们分成若干个队伍，每个队伍至少有k个人。每个人有一个实力值a[i]，每个队伍的矛盾值定义为队内最大实力值减去最小实力值。求所有队伍的矛盾值之和最小化。
解题思路：
首先，我们将所有人的实力值a[i]进行升序排序。接下来，我们使用动态规划来解决这个问题。
设dp[i]表示从前i个人中分配队伍时，矛盾值总和的最小值。状态转移方程如下：
当i是k的倍数时，每支队伍恰好有k个人；否则，必然存在一个队伍人数超过k人。此时，dp[i]的值有两个来源：
- dp[i-1]，意味着第i个人与第i-1个人同队；
- dp[i-k]，意味着第i个人与第i-k+1个人组成一个新队。
初始化时，dp[0]=0，其余位置初始化为无穷大（inf）。从第k个人开始计算dp数组。
附上参考代码：
#include
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=2e5+10;
int a[maxn], dp[maxn];
int main() {
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) dp[i] = inf;
dp[0] = 0;
for (int i = k; i <= n; i++) {
if (i % k == 0) dp[i] = dp[i - k] + a[i] - a[i - k + 1];
else dp[i] = min(dp[i - k] + a[i] - a[i - k + 1], dp[i - 1] + a[i] - a[i - 1]);
}
cout < }
return 0;
}
此外，您还可以参考另一位博主的实现：点击这里
京公网安备 11010802041100号