CodeForce 675C 技巧题（其实我也不知道要归到什么里面去。。。）

         题目大意是有N个银行，这N个银行是呈环状相连的，也就是第1个和第N个是邻居，你在每一个银行里面都有一些钱或者是欠款，这些东西价值的总和为0，你每次只能够把一个银行里面的钱转移的相邻的银行去，求使得所有银行的钱都变成0的最少的移动次数。

        一开始没考虑那么多。。。就直接是把环展开成了链，然后找最长的连续的0，想当然的以为答案就是银行个数减去最长的连续的0，毋庸置疑，结果错掉了。。。

       第二个想法是依然变换为链，然后在每一个长度为N的区间上枚举，毋庸置疑，结果超时了。。。。

       后来问了学长，才发现这个题目的特点，需要用到前缀和。

       其实我是第一次接触“前缀和”这个名词，不过理解大概是这样，第M个位置的前缀和（以下记为sum）就是∑（k = 1 → M）array【k】，恩。由这个式子我们可以看出来，假若sum【i】=sum【j】= a（a是某个常数），那么在区间【i +1 ，j -1】上，这一段区间上的价值之和一定是0（其实拿定义式相减即可）接下来这个题目会要用到。

       这个题目要求我们找到最少移动次数，那么为什么会有最少的移动次数？也就说在移动资金的过程中我们可以省略某一些步骤，那么什么样的步骤可以省略掉？当然是从0移动到0的情况，也就是这个意思，这个N个银行（从 1 开始标号）被划分成了几段，这里仅仅举两段的例子，假设在K，K + 1处把银行划分成了两部分，前一部分的区间和是0，后一部分的区间和也是0，那么前一段区间的移动次数是K - 1，后一段区间的移动次数是 N - K - 1，合起来的移动次数是 N - 2，我们没必要把左边的0 和右边的0 再次进行合并了，因此就少了一个步骤，分成几个区间也是类似的，我们可以看出，分的区间越多，次数是越少的。

       所以，这个问题就转化到求最多有多少个连续区间的和为0了，不要忘了我们的前缀和，假若某一个前缀和a出现的次数是最多的，那么由这个前缀和划分的区间一定能够产生最多的连续区间和为0的区间，因此，这就是这道题目的解法。以下是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
int arr[100010],n,maxm;
long long sum;
map<long long ,int> ma;
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&arr[i]);
for(int i=0;i<n;++i){
sum+=arr[i];
ma[sum]++;
}
for(map<long long ,int>::iterator be=ma.begin();be!=ma.end();++be)
maxm=max(maxm,be->second);
printf("%dn",n-maxm);
return 0;
}

最后

以上就是温暖花卷最近收集整理的关于CodeForce 675C 技巧题（其实我也不知道要归到什么里面去。。。）的全部内容，更多相关CodeForce内容请搜索靠谱客的其他文章。