CF-675

Posted on | Edited on | In | Views:

C. Money Transfers

题意

有n家银行围成一个圈，有个人在有些银行里欠了钱，在一些银行里有存钱，欠的钱总数等于存的钱总数。现在可以有操作，如果两个银行相邻，那么就能在一个银行转任意多的钱到另一个银行。问最少的操作次数，使得在所有银行的存款钱数都为0。

题解

首先我们要发现第一个贪心。如果有一段子串，里面的数字之和等于0，那么在这段子串中移动数字，所需要的代价为子串长度len-1，那么问题就转换成了，我们在这个圈中能找到多少段子串，里面的数字之和等于0，而且段数越多越好，记为k，那么很明显，答案就是n-k，现在问题来了，如何来求满足题意的最大的k。首先，我们考虑用前缀和来存放，如果遇到两个位置，前缀和相等，那么中间那一段数字之和肯定等于0。接下来就是一个跳跃性的思考了，那么如果某个前缀和的值出现了k次，是不是就是我们上述的k呢？答案是正确的！假如有k个位置的前缀和相等，那么中间k-1段子串内数字之和一定都是0，由于总数是0，那么最前面和最后面连着的那一段也肯定是0，所以，我们记录所有的前缀和的值，然后排序。然后用取尺法记录一个数出现的最多次数，就做完了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <strstream>
#define ull unsigned long long
#define ll long long
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forn(i, n) for (int i = n; i >= 0; i--)
#define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define meminf(a) memset(a, inf, sizeof(a))
using namespace std;

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,maxx=1,tmp;
  ll pre=0;
  map<ll,int>log;
  cin>>n;
  for0(i, n){
    cin>>tmp;
    pre+=tmp;
    if (log.count(pre)) {
      log[pre]++;
      maxx=max(maxx, log[pre]);
    }else log[pre]=1;
  }
  cout<<n-maxx<<endl;
  return 0;
}