PKU 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; }