[ SPOJ RESTACK ] Restacking haybales

(\)

Description

---

给出一个环，每个位置有一个初值 (A_i)，有一个目标值 (B_i)，保证 (sum A_i=sum B_i)

每个位置只能把值分给隔壁的，每次分的量都会被计入答案。

• (nle 10^5,A_i,B_ile 10^3)

(\)

Solution

---

先考虑单向传递的情况。

如果一开始 (1) 号节点的个数就是 (A_1) 。

那么手玩以下可以发现第 (i) 个人给第 (i+1) 个人的数量是

[S_i=sum_{j=1}^i(A_j-B_j) ]

然后考虑在此基础上，(n) 号点给 (1) 号点的个数减少了 (k) 。

那么每一个位置的 (S_i) 都减少了 (k) 。

那么我们要最小化的其实是

[sum_{i=1}^n |S_i-k| ]

发现是中位数问题。

(\)

Code

---

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define R register
#define gc getchar
using namespace std;
typedef long long ll;

ll ans;

int n,cst[N];

inline int rd(){
  int x=0; bool f=0; char c=gc();
  while(!isdigit(c)){if(c=='-')f=1;c=gc();}
  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
  return f?-x:x;
}

int main(){
  n=rd();
  for(R int i=1;i<=n;++i){cst[i]=rd();cst[i]-=rd();}
  for(R int i=2;i<=n;++i) cst[i]+=cst[i-1];
  cst[1]+=cst[n];
  sort(cst+1,cst+1+n);
  for(R int i=1;i<=n;++i) ans+=(ll)abs(cst[i]-cst[n/2]);
  printf("%lld
",ans);
  return 0;
}