ABC027: B - 島と橋

abc027b.cpp

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <set>
#include <map>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    int N;
    cin >> N;
    vector<int> vec(N);
    REP(i, N) cin >> vec[i];
    int sum = SUM(vec);
    
    // calculation
    if (sum == 0) {
        cout << 0 << "\n";
    } else {
        if (sum%N == 0) {
            int per_island = sum/N;
            vector<int> partial;
            COPY(vec, partial);  // copy vec to partial
            REP(i, N) {
                partial[i] -= per_island;
            }
            partial_sum(partial.begin(), partial.end(), partial.begin());
            
            int group = 0, bridge = 0;
            REP(i, N) {
                group++;
                if (partial[i] == 0) {
                    bridge += group - 1;
                    group = 0;
                }
            }
            cout << bridge << "\n";
            
        } else {
            cout << -1 << "\n";
        }
    }
    
    return 0;
}