能量传输「CSP多校联考 2019」

题意

在克哈星系的冒险中，(Jim)和他的游骑兵遭遇了虫群的进攻。(Jim)出色的指挥能力使他在兵力严重不足的情况下依旧抗击虫群的多次进攻。但与此同时(Jim)的部分士兵战斗服能源却不足以支持他们继续作战。为了更强的火力压制，(Jim)决定将所有士兵的能源平分，以便所有人都能够参与作战。

已知(Jim)现在有(n)个枪兵，(Jim)将(n)个士兵围成一个圆，所有士兵的能量总和是(n)的倍数，且每次传输只能传输(1)单位的能量。更糟糕的是，充电线的长度是固定的，也就意味着，每次只能让相隔(k)位的两人能量交换。休伯利安号从轨道降落需要非常长的时间，(Jim)希望在在最快的时间知道最少传输次数。

---

思路

把所有可互相到达的点放在一起求解。

假设i需要传给旁边(v_i)，而平均值为(ave)，那么显然有(v_{i+1}=val[i]-ave+v_i)

所以有(v_i=sum_{j=0}^{i-1}val[i]+v_1-(i-1)*ave)，即(v_i=sum_{j=0}^{i-1}val[i]-(i-1)*ave-(-v_i))

这个式子的前半部分显然是可以求得，那么问题在为(v_1)的取值。

这里需要用到一个关于中位数的结论：对于一个数列，使(sum_{i=1}^n|a_i-x|)最小的x为该数列的中位数。

这个的数学证明比较简单。（特别是当都是整数的时候）

那么我们取(v_1)为中位数的相反数即可。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
	#define int long long
	
	const int N=500001;
	
	int n,k,sum,ans;
	int val[N];
	int vis[N],topa,a[N],v[N];

	inline int calc (int now) {
		topa=0;
		while (!vis[now]) {
			vis[now]=1,a[++topa]=val[now];
			now+=k;
			if (now>n) now-=n;
		}
		v[1]=0;
		for (register int i=2; i<=topa; ++i) v[i]=v[i-1]+a[i-1]-sum;
		sort(v+1,v+topa+1);
		int chosen=-v[(topa+1)/2],res=0;
		for (register int i=1; i<=topa; ++i) res+=abs(v[i]+chosen);
		return res;
	}

	inline void MAIN () {
		read(n),read(k),++k;
		for (register int i=1; i<=n; ++i) {
			read(val[i]),sum+=val[i];
		}
		sum/=n;
		for (register int i=1; i<=n; ++i) {
			if (vis[i]) continue;
			ans+=calc(i);
		}
		write(ans);
	}
	
	#undef int
}

int main () {
//    freopen("ore.in","r",stdin);
//    freopen("ore.out","w",stdout);
    Project::MAIN();
}