ABC 027 B - 島と橋

問題

問題概要

省略

解法

まず、すべての住人の数を求めて、それを島の数で割り切れなければ、-1を出力すればいい。また、住民の合計と、島の数から、1つの島に住んでいなければならない人数もわかる。橋を架けなければならない場所の判定は、橋の左側と、右側で住んでいなければならない人数が異なるとき、その場所に橋が必要だということ。ここに、橋を架けなければ、あとの場所をどういじっても、均等に住民を分けることはできない。

ミス

すぐ思いつけなかった。

コード

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int n, a[110];

int main(void){
    cin >> n;
    int sum = 0;
    int memo[110];//memo[i] := i番目までの和
    rep(i, n){
        cin >> a[i];
        sum += a[i];
        memo[i] = sum;
    }

    if(sum % n != 0){
        printf("-1\n");
        return 0;
    }

    int ans = 0;
    int aim = sum / n;//1つの島に必要な人数
    for (int i = 0; i < n - 1; ++i){
        int l = memo[i], r = sum - memo[i];//橋を挟んで左側と右側に必要な人の数
        if(l == aim * (i + 1) && r == aim * (n - (i + 1))) continue;
        ans++;
    }

    printf("%d\n", ans);
    return 0;
}