算法竞赛入门经典训练指南第5页，已经说的很清楚了，我就是把他说的不用存A数组的方案实现一下
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll ans; const int maxn=1000000+10; int c[maxn]; int n; int main() { while(~scanf("%d",&n)) { ll sum=0; c[0]=0;//x1-0,即x1 ll a; for(int i=1;i<=n;i++) { scanf("%lld",&a); sum+=a; c[i]=c[i-1]+a; } ll m=sum/n; for(int i=1;i<n;i++) c[i]-=m*i; sort(c,c+n); ll x1=c[(n-1)/2]; ans=0; for(int i=0;i<n;i++) { ans+=abs(x1-c[i]); } printf("%lld\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7289449.html
相关资源：数据结构—成绩单生成器