先不考虑是隔$k$个人，直接当成每次逆时针加$k$。那么原图中的$n$个人划分为若干个环，每个环都是独立的，这里取一个四元环继续讲解。
假设四个人原先有的钱为$S_i$，逆时针收到的钱为$x_i$（负数即反向），需要达到平均值$A$，那么有
$$
\left\{
\begin{array}{c}
S_1+x_1-x_2=A \\
S_2+x_2-x_3=A \\
S_3+x_3-x_4=A \\
S_4+x_4-x_1=A
\end{array}
\right.
$$
一行一行加，解得：
$$
\left\{
\begin{array}{c}
x_1=&x_1 &\triangleq x_1-y_1 \\
x_2=&x_1-(A-S_1) &\triangleq x_1-y_2 \\
x_3=&x_1-((A-S_1)+(A-S_2)) &\triangleq x_1-y_3 \\
x_4=&x_1-((A-S_1)+(A-S_2)+(A-S_3)) &\triangleq x_1-y_4
\end{array}
\right.
$$
这个环所需要的总时间为$T=|x_1|+|x_2|$ $+|x_3|+|x_4|$ $=|x_1-y_1|+|x_1-y_2|$ $+|x_1-y_3|+|x_1-y_4|$，由绝对值数形结合的知识可知当$x_1$取$y_i$的中位数（不计平均）时该式最小。
对于这道题，可以先求出总的平均值$A$，然后每个环都用这个$A$列方程和验证，答案累加即可。
最后说一下$k$的问题，题意不是很清晰，最终确定隔$n-1$个人是可以的（相当于相邻），隔$n$个人是不可以的（没有实际意义）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
ll s[N];
bool vis[N];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
++k;
ll sum=0;
for (int i=0;i<n;i++) {
scanf("%lld",&s[i]);
sum+=s[i];
}
if (sum%n) {
puts("gg");
return 0;
}
ll A=sum/n,ans=0;
int cnt=0;
for (int i=0;i<n;i++) {
cnt+=(s[i]==A);
}
if (cnt==n) {
puts("0");
return 0;
}
if (k>n) {
puts("gg");
return 0;
}
bool good=true;
for (int i=0;i<n;i++) {
if (vis[i]) continue;
int j=i;
ll tmp=0;
vector<ll> ve;
do {
vis[j]=true;
tmp+=A-s[j];
ve.push_back(tmp);
j=(j+k)%n;
} while (j!=i);
if (tmp) {
good=false;
break;
}
sort(begin(ve),end(ve));
ll x=ve[ve.size()/2];
for (auto y:ve) {
ans+=abs(x-y);
}
}
if (!good) {
puts("gg");
} else {
printf("%lld\n",ans);
}
return 0;
}
|
