Codeforces Round #353 (Div. 2) C Money Transfers

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：

http://www.codeforces.com/contest/675/problem/C

题意：

给一个数组，每个数与他相邻的数相连，第一个与最后一个相连，每个数的数值可以左右移动，问最少的移动次数使所有的数都为零。

题解：

把数组分成若干个部分，每个部分和都为0，每部分最多移动len-1，这样分的越多，得到的结果就越优。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

const int maxn=;

typedef __int64 LL;

int n;

LL sum[maxn];

int arr[maxn];

map<LL,int> mp;

void init(){

    mp.clear();

}

int main(){

    while(scanf("%d",&n)==&&n){

        init();

        for(int i=;i<=n;i++){

            scanf("%d",arr+i);

        }

        sum[]=arr[];

        mp[sum[]]++;

        int ma=;

        for(int i=;i<=n;i++){

            sum[i]=sum[i-]+arr[i];

            mp[sum[i]]++;

            if(mp[sum[i]]>ma) ma=mp[sum[i]];

        }

        int ans=n-ma;

        printf("%d\n",ans);

    }

    return ;

}