条形均分纸牌
题目大意：
给定n堆纸牌，每一堆的纸牌个数为ai，你可以从一堆中取出一张纸牌放到其前一堆（ai = ai-1 , ai-1 = ai-1+1）或者放到其后一堆（ai = ai-1, ai+1 = ai+1 +1），询问最少的操作次数使得纸牌均分？
思路：
设 sum = a数组的总和
1.首先判断
无解
的情况，sum不能被n整除，即
sum%n != 0
2.
有解
的情况，即
sum%n == 0
，设m = sum/n
那么我们的目标就是
a1,a2,a3 ... an => m,m,m ... m
首先考虑第一个人
如果a1 > m 那么为了使a1 => m ，需要
a
1
=
a
1
−
(
a
1
−
m
)
,
a
2
=
a
2
+
(
a
1
−
m
)
a1 = a1 – (a1-m),a2 = a2+(a1-m)
a
1
=
a
1
−
(
a
1
−
m
)
,
a
2
=
a
2
+
(
a
1
−
m
)
，
即从第一堆纸牌中拿走(a1-m)张纸牌，放到第2堆纸牌中
如果a1 <= m 那么同理为了使a1 => m, 需要
a
1
=
a
1
+
(
m
−
a
1
)
,
a
2
=
a
2
+
(
m
−
a
1
)
a1 = a1 + (m-a1),a2 = a2 +(m-a1)
a
1
=
a
1
+
(
m
−
a
1
)
,
a
2
=
a
2
+
(
m
−
a
1
)
即从第二堆纸牌中拿(m-a1)张，放到第1堆纸牌中
根据以上规则同样可以模拟第2~n堆纸牌的过程，那么其中可能会存在一种 ai 为负数的情况，这个时候就可以考虑
ai先从ai+1中拿了相应的纸牌再给前面的纸牌堆。
如此就可以得到如下表达式
∑
1
n
∣
i
∗
m
−
s
u
m
[
i
]
∣
（
m
=
s
u
m
[
n
]
/
n
,
s
u
m
[
i
]
为
a
的
前
缀
数
组
）
\sum_1^n| i*m – sum[i] | （m=sum[n]/n,sum[i]为a的前缀数组）
1
∑
n
∣
i
∗
m
−
s
u
m
[
i
]
∣
（
m
=
s
u
m
[
n
]
/
n
,
s
u
m
[
i
]
为
a
的
前
缀
数
组
）
等价于
∑
1
n
∣
f
[
i
]
∣
（
f
[
i
]
为
数
组
a
每
个
元
素
都
减
去
m
后
的
前
缀
数
组
）
\sum_1^n| f[i] | （f[i]为数组a每个元素都减去m后的前缀数组）
1
∑
n
∣
f
[
i
]
∣
（
f
[
i
]
为
数
组
a
每
个
元
素
都
减
去
m
后
的
前
缀
数
组
）
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int f[N];
int n;
int main()
{
cin >> n;
int sum = 0,ans = 0;
for(int i=1;i<=n;++i) cin >> a[i], sum += a[i];
int p = sum/n;
f[0] = 0;
for(int i=1;i<=n;++i) f[i] = f[i-1] + (a[i]-p);
for(int i=1;i<=n;++i) ans += fabs(f[i]);
cout << ans << endl;
}
环形均分纸牌
例题：
糖果传递
环形均分纸牌问题就是在普通均分纸牌的基础上加了一个条件就是第1堆可以和第n堆进行纸牌交换
1.暴力做法
那么考虑各种环形问题的普遍解法，暴力n次求以第i堆纸牌为首（1<=i<=n）时的条形均分纸牌问题,时间复杂度为
O
(
N
2
)
O(N^2)
O
(
N
2
)
2.
设A数组为a数组每个元素均减去m
sum数组为A数组的前缀和
考虑以k为首的条形均分纸牌，有
| 第i堆 | 前缀和 |
|---|---|
| k | sum[k] – sum[k-1] |
| k+1 | sum[k+1] – sum[k-1] |
| k+2 | sum[k+2] – sum[k-1] |
| … | … |
| n | sum[n] – sum[k-1] |
| 1 | sum[n] – sum[k-1] + sum[1] |
| 2 | sum[n] – sum[k-1] + sum[2] |
| … | … |
| k-1 | sum[n] – sum[k-1] + sum[k-1] |
由于sum[n] = 0故问题可以转换为求
∑
1
n
∣
s
u
m
[
i
]
−
s
u
m
[
k
]
∣
的
最
小
值
\sum_1^n | sum[i]-sum[k]|的最小值
1
∑
n
∣
s
u
m
[
i
]
−
s
u
m
[
k
]
∣
的
最
小
值
利用中位数的思想，对sum数组排序后取 k = （n+1) / 2即是答案。
时间复杂度为
O
(
N
l
o
g
N
)
O(NlogN)
O
(
N
l
o
g
N
)
/*
环形均分纸牌问题
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N],s[N];
int n;
int main()
{
scanf("%d",&n);
long long sum = 0,ans = 0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum += a[i];
int p = sum/n;
s[0] = 0;
for(int i=1;i<=n;++i) s[i] = s[i-1] + (a[i]-p);
sort(s+1,s+1+n);
int k = (n+1)/2;
for(int i=1;i<=n;++i) ans += abs(s[i]-s[k]);
printf("%lld\n",ans);
}