Algoogle

Algorithm for Programming Contest

PKU 3671 Dining Cows

Category: PKU Tag: implementation

Dining Cows

問題概要


解法


1と2の境界をすべてチェックする.
1の個数を各位置までそれぞれもつ

コード


(3671.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <cstdio>

using namespace std;

int N, D, ans, cnt[30010];

int main(){
    scanf("%d", &N);
    ans = N + 1;
    for(int i = 0; i < N; i++){
        scanf("%d", &D);
        cnt[i+1] = cnt[i] + D % 2;
    }
    for(int i = 0; i <= N; i++)
        ans = min(ans, cnt[N] + i - 2*cnt[i]);
    printf("%d\n", ans);
    return 0;
}

Comments