經典貪心
設第x人給他右邊的人xi個金幣，因為最后每個人的金幣數ave易知，所以可以得到n個方程： a1+xn-x1=ave a2+x1-x2=ave ….. 設bi=ai-ave 得 x1=xn+b1 x2=x1+b2=xn+b1+b2 …. 設
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;const int maxn = 110000;int a[maxn],n;ll as[maxn];int main(){ scanf("%d",&n); ll s=0; for(int i=1;i<=n;i++) { int x; scanf("%d",&x); a[i]=x; s+=x; } s/=(ll)n; ll ave=s; s=0; for(int i=1;i<n;i++) { s+=a[i]-ave; as[i]=-s; } as[n]=0; sort(as+1,as+n+1); ll ans; if(n&1) ans=as[n/2+1]; else ans=(as[n/2]+as[n/2+1])/2; ll ret=0; for(int i=1;i<=n;i++) ret+=abs(ans-as[i]);新聞熱點
疑難解答
