P3051 [USACO12MAR]Haybale Restacking G
yxy_
·
·
题解
大意：
从原来的环形数列变成目标数列，对于所有物品，每移动一个单位，移动距离 x 花费为 x。
求变换成目标序列的最小花费。
思考：
移动距离 = 花费，那就是相邻位置之间传递一单位物品，花费为1。
于是题意转化为：相邻位置间相互传递，使得原序列变成目标序列。求最小移动的数量总和。
为糖果传递的一个变式题。
设 x_i 为最终从 i 位置传递到 i+1 位置的总干草数量。则：
目标数量 $=$ 该位置原数量 $-$ 传递到下一位置的总数量 $+$ 上一位置传递过来的总数量。
$B_1 = A_1 - x_1 + x_n$；
$\Rightarrow$ $ x_1 = x_n + A_1 - B_1$；
$B_2 = A_2 - x_2 + x_1$；
$\Rightarrow$ $ x_2 = x_1 + A_2 - B_2 = x_n + A_1 + A_2 - B_1 - B_2$；
$B_3 = A_3 - x_3 + x_2$；
$\Rightarrow$ $ x_3 = x_2 + A_3 - B_3 = x_n + A_1 + A_2 + A_3 - B_1 - B_2 - B_3$；
$...
$\Rightarrow$ $ x_n = x_{n-1} + A_n - B_n = x_n + A_1 + A_2 +...+ A_n - B_1 - B_2 -...- B_n$；
要使移动的数量总和最小：
即 $x_1 + x_2 + x_3 + ... + x_n$ 最小，令 $C_i = B_i - A_i$，则：
$|x_n - C_1| + |x_n - C_1 - C_2| + |x_n - C_1 - C_2 - C_3| + ... + |x_n - C1 - C_2 -...-C_n|$ 最小。
$C_i$ 维护前缀和 $S_i$，则使：
$|x_n - S_1| + |x_n - S_2| + ...+ |x_n - S_n|$ 最小。
**绝对值不等式**，当 $x_n$ 为 $S_1,S_2...S_n$ 中位数的时候，总和最小。
---
### Code：
```
#include<iostream>
using namespace std;
const int N=200010;
int n,m,a[N], b[N], c[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
for(int i=1;i<=n;i++) c[i]=b[i]-a[i], c[i]+=c[i-1]; //差值、前缀
sort(c+1,c+n+1);
int mid=c[n/2+1]; //取中位数
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=abs(mid-c[i]);
}
cout<<ans;
return 0;
}
```
---
三倍经验：
[糖果传递](https://www.luogu.com.cn/problem/P2512)、
[士兵站队](https://www.luogu.com.cn/problem/P1889)。