Codeforces353-div2C Money Transfers

Problem - C - Codeforces

There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than . Also, bank 1 and bank n are neighbours if n  > 1. No bank is a neighbour of itself.

隣接した場所の値を自由に交換出来る時，数列を全部にするには最小何回で出来るか．
円環なので，切って つ繋げて表現した．最初は累積和を取って， となる区間で移動させるようにしていた．これはそれぞれの の和が答えで，つまり となる．
累積和が となる場所の個数は，累積和を開始する地点による．

上の図(適当)は，累積和をカウントしたものとする．開始地点をずらすというのは，赤の線をどこに引くか( となる基準をどこにするか)ということになる．よって，最初の累積和の数の個数を数えて，そのmaxを から引く．

Code

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 <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  vector<ll> v(n);
  rep(i, n) cin >> v[i];


  ll imos[100005];
  memset(imos, 0, sizeof(imos));
  imos[0] = v[0];

  REP(i, 1, n) {
      imos[i] += imos[i-1] + v[i];
  }

  map<ll, int> m;
  int x = 0;

  rep(i, n) {
      m[imos[i]]++;
      x = max(x, m[imos[i]]);
  }

  cout << n - x << endl;

  return 0;
}
May 17th, 2016
codeforces, いもす法