\(\\\)
Description
给出一个环，每个位置有一个初值 \(A_i\)，有一个目标值 \(B_i\)，保证 \(\sum A_i=\sum B_i\)
每个位置只能把值分给隔壁的，每次分的量都会被计入答案。
- \(n\le 10^5,A_i,B_i\le 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\n",ans);return 0;
}