PKU 3671 Dining Cows

3671 -- Dining Cows

[問題]
1または2がランダムにN個並んでいる。任意の箇所を1 -> 2 もしくは 2 -> 1と書き換えることで、全ての1が2より前に来るようにしたい。
書き換える回数の最小値を求めよ。

[解法]

1グループと2グループをどこで分けるかで全探索。書き換える必要のある数字は少し工夫するとO(1)で求まる。

1,2を0,1に置き換えて、前半はその区間の合計(1の数)、後半は数字の個数(全てを1と仮定する) - 1の個数　みたいなことをすると計算量が落ちる。

int N;
vector<int>Cow;
int sum[30000];
int main(){
  cin>>N;
  rep(i,N){
    int t; cin>>t;
    t--;
    Cow.pb(t);
  }
  sum[0] = Cow[0];
  //sum[i] := sum[0,i]
  rep(i,Cow.size() - 1)
    sum[i + 1] = sum[i] + Cow[i + 1];
  //[0,x),[x,N)
  int ans = INF;
  rep(x,Cow.size() + 1){
    int up,down;
    up = down = 0;
    if(x > 0) up = sum[x - 1];
    down = sum[Cow.size() - 1] - up;
    down = N - x - down;
    ans = min(ans,up + down);
  }
  cout<<ans<<endl;
}