做题感悟:感觉完全没想到这种方法,竟然可以这样做!!
解题思路:这里不做解释(算法指南中有解释)。
代码:
#include<stdio.h> #include<iostream> #include<map> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; const int INF = 99999999 ; const int MX = 1000005 ; int g[MX],c[MX] ; int main() { int n ; while(~scanf("%d",&n)) { long long sum=0 ; memset(g,0,sizeof(g)) ; memset(c,0,sizeof(c)) ; for(int i=1 ;i<=n ;i++) { scanf("%d",&g[i]) ; sum+=(long long)g[i] ; } int M=sum/n ; for(int i=1 ;i<n ;i++) c[i]=c[i-1]+g[i]-M ; sort(c,c+n) ; int x1=c[n/2] ; long long ans=0 ; for(int i=0 ;i<n ;i++) ans+=abs(x1-c[i]) ; printf("%lld\n",ans) ; } return 0 ; }