P2512 [HAOI2008]糖果传递 题解
D愚者
2019-05-14 17:28:37
### - 前言：
1. 看到这题，首先想到费用流，然后....~~妥妥的MLE~~
------------
30分Code：
------------
```cpp
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
long long n,sum,cnt=-1,mincost;
long long x[1000100],st[1000100],dis[1000100],vis[1000100],pre[1000100],last[1000100],flow[1000100];
struct edge{
long long to,next,val,flow;
}e[10001000];
void add(long long u,long long v,long long flow,long long val){
e[++cnt].to=v;
e[cnt].flow=flow;
e[cnt].val=val;
e[cnt].next=st[u];
st[u]=cnt;
}
void Add(long long u,long long v,long long flow,long long val){
add(u,v,flow,val);
add(v,u,0,-val);
}
bool spfa(long long s,long long t){
queue<int> q;
for(long long i=1;i<=n+1;i++)
dis[i]=2147483647;
q.push(s);
vis[s]=true;
pre[s]=0;
pre[t]=-1;
dis[s]=0;
flow[s]=2147483647;
while(!q.empty()){
long long u=q.front();
q.pop();
vis[u]=false;
for(long long i=st[u];i!=-1;i=e[i].next){
long long v=e[i].to;
if(e[i].flow>0&&e[i].val+dis[u]<dis[v]){
dis[v]=dis[u]+e[i].val;
pre[v]=u;
last[v]=i;
flow[v]=min(flow[u],e[i].flow);
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
return pre[t]!=-1;
}
void dinic(long long s,long long t){
while(spfa(s,t)){
long long now=t;
mincost+=flow[t]*dis[t];
while(now!=s){
e[last[now]].flow-=flow[t];
e[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main(){
memset(st,-1,sizeof(st));
scanf("%lld",&n);
long long s=0,t=n+1;
for(long long i=1;i<=n;i++){
scanf("%lld",&x[i]);
sum+=x[i];
}
sum/=n;
for(long long i=1;i<=n;i++)
x[i]-=sum;
for(long long i=1;i<=n;i++){
if(x[i]>0)
Add(s,i,x[i],0);
if(x[i]<0)
Add(i,t,-x[i],0);
}
for(long long i=1;i<=n;i++){
if(i!=1)
Add(i,i-1,2147483647,1);
if(i!=n)
Add(i,i+1,2147483647,1);
}
Add(1,n,2147483647,1);
Add(n,1,2147483647,1);
dinic(s,t);
printf("%lld",mincost);
return 0;
}
```
------------
### - 正解：
------------
- 首先，最终每个小朋友的糖果数量可以计算出来，等于糖果总数除以n，假设C1=A1减去最终每个小朋友的糖果数量，设Xi表示第i个小朋友给了第i-1个小朋友Xi颗糖果，
- 我们希望Xi的绝对值之和尽量小，即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小。注意到|X1-Ci|的几何意义是数轴上的点X1到Ci的距离，所以问题变成了：给定数轴上的n个点，找出一个到他们的距离之和尽量小的点，而这个点就是这些数中的中位数，~~证明应该都懂~~。
------------
Code：
------------
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[1000100],x[1000100];//注意数据范围
long long mid,ans,n,sum;
int absolute(int x){//手打abs
if(x<0)
return -x;
return x;
}
int main(){
scanf("%lld",&n);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
}
sum/=n;//求最终每个小朋友的糖果数量可以计算出来
for(long long i=1;i<=n;i++)
x[i]=x[i-1]-a[i]+sum;
sort(x+1,x+1+n);
mid=x[(n+1)/2];//中位数
for(long long i=1;i<=n;i++)
ans+=absolute(x[i]-mid);//求最小代价
printf("%lld",ans);
return 0;
}
```