洛谷P3051 [USACO12MAR]Haybale Restacking 题解

description：

solution：

code:

#include<cstdio>
#include<algorithm>

using namespace std;
int a[100005],b[100005],c[100005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
	}
	for(int i=2;i<=n;i++)
	{
		c[i]=c[i-1]+b[i]-a[i];
	}
	sort(c+1,c+n+1);
	int tmp=c[(n+1)/2];
	int x=-tmp;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=abs(c[i]+x);
	}
	printf("%lld\n",ans);
	return 0;
}