Codeforces 675C Money Transfers 思维题-白红宇

Codeforces 675C Money Transfers 思维题

阅读量：5348 次

发布时间：2019-06-15

本文共 634 字，大约阅读时间需要 2 分钟。

原题：http://codeforces.com/contest/675/problem/C

　　让我们用数组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
     
       2 #include
       3 #include
       
         4 using namespace std; 5 int main(){ 6     int n; 7     scanf("%d",&n); 8     map
        
         mp; 9     int ans = n-1;//初始情况下整个数组为一个区间10     int t;11     long long sum = 0;12     for(int i = 0;i

转载于:https://www.cnblogs.com/zqy123/p/5503280.html

你可能感兴趣的文章