P3051 [USACO12MAR]Haybale Restacking G

知识点：环形均分纸牌

难度：5

这个题乍一看不是均分纸牌，其实是一样的，题目的意思是把每个数变成目标数字，并且两个序列的和是一样的，只能左右交换的，那么从这两个信息就可以看出跟环形均分纸牌很像，然后经过思考这个问题可以等价转换，也就是让a减去b得到c，那么题目的问法就可以转化为，让c序列全部变为0，可以循环邻项交换，最少的交换次数是多少，这就是一个环形均分纸牌问题，只不过和是零，不需要减去均值了，可以直接求前缀和了，

那么代码其实很好写的，就是一定要看出这个问题可以转化为环形均分纸牌问题，怎么看出，关键的两点，1，两个序列的和是一样的，2，序列是围成一个环形的，可以邻项交换，

#include 
 
using namespace std;
 
const int N = 1e5 + 5;
 
int a[N];
 
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		a[i] = x - y;
		a[i] += a[i - 1];
	}
	sort(a + 1, a + n + 1);
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += abs(a[i] - a[(n + 1) / 2]);
	}
	cout << ans;
	return 0;
}