【题解】HackerRank - Fair Cut

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/fair-cut

题意

给 n 个数，分成 k 和 n - k 两组，使得两个组之间任意数对之差的绝对值之和最小。

题解

  • 将问题转化为对于两组数每组内部元素两两之差的绝对值之和的和最大
  • 排个序把绝对值去了
  • 对于一组有 k 个元素有序的数，两两之差之和的值为 Sum[a[i] * (2i + k - 1), {i, 1, k}]
  • dp[i][j] 表示第一组取 i 个数，第二组取 j 个数 （可以开成滚动数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int maxn = 3000 + 5;
LL dp[maxn][maxn], n, k, a[maxn];

int main() {
    cin >> n >> k;
    FOR(i, 0, n) cin >> a[i];
    sort(a, a + n);
    FOR(i, 0, k + 1)
        FOR(j, 0, n - k + 1) {
            dp[i][j] = (i || j) ? -1E18 : 0;
            if (i) dp[i][j] = max(dp[i - 1][j] + a[i + j - 1] * (2 * i - k - 1), dp[i][j]);
            if (j) dp[i][j] = max(dp[i][j - 1] + a[i + j - 1] * (2 * j - (n - k) - 1), dp[i][j]);
        }
    LL ans = -dp[k][n - k];
    FOR(i, 0, n) ans += a[i] * (2 * i - n + 1);
    cout << ans << endl;
}