题目链接：https://www.luogu.com.cn/problem/P4016

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=211,M=4011,inf=1<<29;
 4 int n,m,st,ed,a[N],sum,maxflow,ans;
 5 int to[M],nxt[M],c[M],w[M],edge,head[N];
 6 int pre[N],incf[N],dis[N];
 7 bool vis[N];
 8 
 9 inline int re_ad() {
10     char ch=getchar(); int x=0,f=1;
11     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
12     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
13     return x*f;
14 }
15 
16 inline void addedge(int x,int y,int cc,int ww) {
17     ++edge,to[edge]=y,nxt[edge]=head[x],c[edge]=cc,w[edge]=ww,head[x]=edge;
18     ++edge,to[edge]=x,nxt[edge]=head[y],c[edge]=0,w[edge]=-ww,head[y]=edge;
19 }
20 
21 inline void print_test() {
22     for(int i=0;i<=n;++i) printf("%d ",dis[i]); puts("");
23     for(int i=0;i<=n;++i) printf("%d ",incf[i]); puts("");
24     for(int i=0;i<=n;++i) printf("%d ",pre[i]); puts("");
25 }
26 
27 inline bool SPFA() {
28 //    printf("awa\n");
29     memset(vis,false,sizeof(vis));
30     memset(dis,0x3f,sizeof(dis));
31     memset(incf,0x3f,sizeof(incf));
32     queue<int> q;
33     q.push(st);
34     dis[st]=0,vis[st]=true;
35     int u,v;
36     while(!q.empty()) {
37         u=q.front();
38         vis[u]=false,q.pop();
39         for(int i=head[u];i;i=nxt[i]) {
40             if(!c[i]) continue;
41             v=to[i];
42             if(dis[u]+w[i]<dis[v]) {
43                 dis[v]=dis[u]+w[i];
44                 incf[v]=min(incf[u],c[i]);
45                 pre[v]=i;
46                 if(!vis[v]) vis[v]=true,q.push(v);
47             }
48         }
49     }
50 //    print_test();
51     if(dis[ed]==0x3f3f3f3f) return false;
52     return true;
53 }
54 
55 inline void Update() {
56     int lj=ed,i;
57     while(lj!=st) {
58         i=pre[lj];
59         c[i]-=incf[ed],c[i^1]+=incf[ed];
60         lj=to[i^1];
61     }
62     maxflow+=incf[ed];
63     ans+=dis[ed]*incf[ed];
64 }
65 
66 int main()
67 {
68     n=re_ad();
69     for(int i=1;i<=n;++i) a[i]=re_ad(),sum+=a[i];
70     sum/=n,st=0,ed=n+1,edge=1;
71     for(int i=1;i<=n;++i) a[i]-=sum;
72     for(int i=1;i<=n;++i) {
73         if(a[i]>0) addedge(st,i,a[i],0);
74         if(a[i]<0) addedge(i,ed,-a[i],0);
75     }
76     int ll,rr;
77     for(int i=1;i<=n;++i) {
78         ll=(i!=1)?i-1:i+n-1,rr=(i!=n)?i+1:i+1-n;
79         addedge(i,ll,inf,1);
80         addedge(i,rr,inf,1);
81     }
82     while(SPFA()) Update();
83     printf("%d\n",ans);
84     return 0;
85 }

 1 #include<bits/stdc++.h>
 2 #define il inline
 3 #define ll long long
 4 using namespace std;
 5 const int N=105;
 6 ll n,a[N],sum,s[N];
 7 int main()
 8 {
 9     ios::sync_with_stdio(0);
10     cin>>n;
11     for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
12     sum/=n;
13     for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i];
14     sort(s+1,s+n+1);
15     sum=0;
16     for(int i=1;i<=n;i++)sum+=abs(s[n/2+1]-s[i]);
17     cout<<sum;
18     return 0;
19 }