PKU 3671 Dining Cows
http://poj.org/problem?id=3671
n匹の牛が順番に並んでいる。最初にi番目の牛は1か2のグループに割り当てられている。
このとき、牛のグループ割り当てをi番目までの牛が全て1で、i+1番目以降の牛が全て2となるように変更したい。全て1や全て2とうパターンも可能。その条件のもと、割り当てを変更しなければならない最小の牛は何匹かを答える問題。
n<=30000と大きいので、O(n)かO(nlogn)程度でないとアウト。
グループ1とグループ2の境目を指定したとき、うまいことやればO(1)で変更する牛の数がわかるのでO(n)で答えが出せる。
int in[30000]; main(){ int n; cin>>n; int num2=0; rep(i,n){ cin>>in[i]; if(in[i]==2)++num2; } int ans=num2; int tnum2=0; rep(i,n){ ans=min(ans,tnum2*2+n-i-num2); if(in[i]==2)++tnum2; } cout<<ans<<endl; }