Codeforces round #353div2 C

题目来源：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=117863#problem/C

题目大意：给你n个数字，代表这个人在n个银行里面的存款数目，这些银行围成一个环，银行里面的资金

可以流向他周围的银行，问你最少要流动多少次，才能使得所有银行里的存款都是0。

思路分析：要将环分割成多个和为0的分组分别处理，每一个和为0分组，操作次数是分组大小-1

如果最终分了k组，那么操作次数就是n-k，很显然k越大，操作次数越少，现在问题就变成了最多能

分成多少个和为0的分组，关于这个问题，可以用前缀和实现，和为0的区间的个数==前缀和相等的

个数，证明很容易。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int maxn=100000+100;
int a[maxn];
map<long long,int> m;
int main()
{
    int n;
    __int64 sum;
    int ma=0;
      scanf("%d",&n);
        sum=0;
        int ans=n-1;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            m[sum]++;
            ma=max(ma,m[sum]);
            ans=min(ans,n-m[sum]);
        }
        printf("%d\n",ans);
}

巴特西

Codeforces round #353div2 C

最新文章

热门文章