题目传送门:http://cojs.tk/cogs/problem/problem.php?pid=741
虽然是“网络流24题”之一,然而可以O(n)搞
来来来,我们一起来推式子!
6541324587
#include<bits/stdc++.h> using namespace std; const int N = 100+9; int n,arr[N],sum,vout,sta; inline int read(){ char c=getchar(); int ret = 0, f = 1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ freopen("overload.in","r",stdin); freopen("overload.out","w",stdout); n = read(); for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n; for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1]; nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2]; for (int i=1;i<=n;i++) vout += abs(arr[i]-sta); cout<<vout<<endl; return 0; }
感觉真的是好神奇啊!
I have been exploring for a little bit for any high-quality articles or blog posts on this kind of area . Exploring in Yahoo I at last stumbled upon this web site. Reading this information So i’m happy to convey that I’ve a very good uncanny feeling I discovered exactly what I needed. I most certainly will make sure to do not forget this site and give it a glance regularly.