Codeforces 675C Money Transfers 思维题

Codeforces 675C Money Transfers 思维题

原题：

　　让我们用数组a保存每个银行的余额，因为所有余额的和加起来一定为0，所以我们能把整个数组a划分为几个区间，每个区间的和都为0。对于每个区间来说，设该区间长度为l，则让该区间都为0的操作数为l-1，例如：1 、1 、-3 、1的操作数为3，也就是说，若把a分成k个区间，则a所需要的总的操作数为n-k。

　　所以现在我们的目标就是把数组a划分为尽可能多的部分，这个时候我们可以用一个map，统计前缀和的个数，因为对于有若干个和为0的区间的前缀和是相同的，例如：1 、-1和1 、-1 、2 、-2。

 1 #include<stdio.h>
 2 #include<map>
 3 #include<algorithm>
 4 using namespace std;
 5 int main(){
 6     int n;
 7     scanf("%d",&n);
 8     map<long long,int>mp;
 9     int ans = n-1;//初始情况下整个数组为一个区间
10     int t;
11     long long sum = 0;
12     for(int i = 0;i<n;i++){
13         scanf("%d",&t);
14         sum += t;
15         mp[sum]++;
16         ans = min(ans,n-mp[sum]);
17     }
18     printf("%d",ans);
19     return 0;
20 }

转载于:.html