题目链接
环形均分纸牌……
先将每堆纸牌的牌数减去其平均数 $ dfrac{sum_{i = 1}^na[i]}{n} $。
对于环形问题，首先考虑切开。假定我们从 $ k $ 切开，则为 $ A[k+1],A[k+2],...,A[n],A[1],...,A[k] $ ，其前缀和为 $ S[k+1]−S[k], S[k+2]−S[k],...,S[n]−S[k],S[1]+S[n]−S[k],...,S[n] $ 。
由于均分之后， $ S[n]=0 $ 恒成立，所以前缀和的变化仅仅是减去 $ S[k] $。那么，我们要求的就是哪个取值上最短，换言之，求什么时候 $ sum_{i=1}^n∣S[i]−S[k]∣ $ 取到最小。
答案是在中位数处取到，从中位数的位置变化到靠下的位置或是靠上的位置，都会使某一部分点的距离增大。所以这里转化为求中位数，也就是求第 $ dfrac{n + 1}{2} $ 大的元素。
代码：
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 10;
long long n, a[maxn], cnt[maxn], sum, t, ans;
inline int read() {
register char ch = 0; register int w = 0, x = 0;
while( !isdigit(ch) ) w |= (ch == '-'), ch = getchar();
while( isdigit(ch) ) x = (x * 10) + (ch ^ 48), ch = getchar();
return w ? -x : x;
}
inline long long Abs(long long x) { return x > 0 ? x : -x; }
int main(int argc, const char *argv[])
{
freopen("..\nanjolno.in", "r", stdin);
freopen("..\nanjolno.out", "w", stdout);
scanf("%lld", &n);
for(int i = 1; i <= n; ++i) a[i] = a[n + i] = read(), sum = sum + a[i];
sum = sum / n;
for(int i = 1; i <= n; ++i) a[i] = a[i] - sum, cnt[i] = cnt[i - 1] + a[i];
sort(cnt + 1, cnt + n + 1), t = cnt[(n + 1) >> 1];
for(int i = 1; i <= n; ++i) ans = ans + Abs(t - cnt[i]);
printf("%lld
", ans);
fclose(stdin), fclose(stdout);
return 0;
}
同样思想的问题还有带权中位数问题……不过这里还用到了类似区间 $ DP $ 的 $ DP $ ……
Luogu_2803
$ dp[i][j] $ 表示第 $ i $ 栋楼房前已经分了 $ j $ 个区间（每个区间的楼房全部通往该区间的一个学校）；
$ dp[i][j]=dp[k-1][j-1]+pos[k][i] (（) k $ 为最新区间的起始点）；
需要预处理出每个区间 $ [a,b] $（每个区间的楼房全部通往该区间的一个学校）的最优状态 $ pos[a][b] $。
代码：
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100 + 10;
int n, k, num[maxn], sum_num[maxn], dis[maxn], sum_dis[maxn], pos[maxn][maxn], dp[maxn][maxn];
int main(int argc, const char *argv[])
{
freopen("..\nanjolno.in", "r", stdin);
freopen("..\nanjolno.out", "w", stdout);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%d", &num[i]), sum_num[i] = sum_num[i - 1] + num[i];
for(int i = 2; i <= n; ++i) scanf("%d", &dis[i]), sum_dis[i] = sum_dis[i - 1] + dis[i];
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) {
int p = j, sum = 0;
while( p < i && sum_num[p] - sum_num[j - 1] < sum_num[i] - sum_num[p] ) ++p;
for(int k = j; k <= i; ++k)
if( k <= p ) sum = sum + num[k] * (sum_dis[p] - sum_dis[k]);
else sum = sum + num[k] * (sum_dis[k] - sum_dis[p]);
pos[j][i] = sum;
}
for(int i = 1; i <= n; ++i) {
dp[i][1] = pos[1][i];
for(int j = 2, minn = 0x3f3f3f3f; j <= k; ++j) {
for(int k = 1; k <= i; ++k) minn = min(minn, dp[k - 1][j - 1] + pos[k][i]);
dp[i][j] = minn;
}
}
printf("%d
", dp[n][k]);
fclose(stdin), fclose(stdout);
return 0;
}
—— 即使这些只是昙花一现的回忆，那时的我却以此为信仰。