ARC082 D : Derangement(400)
作成日：2017.09.03
最終更新日：2017.09.03
問題概要
1,2,...,Nの順列p1,p2,...pNが与えられる。
操作「順列で隣り合う二つの数を選んで入れ替える」を0回以上行うことで、すべてのiにおいてpi≠iとなるようにする。
必要な操作の最小回数を求めよ。
制約
2≤N≤105
数列{pi}は1,2,...,Nの順列
考え方
pi=iである時はpi−1あるいはpi+1と入れ替えなければならない。
この時pi−1≠i,pi+1≠iであることから、piに対しては1回だけ操作を行えば良い。
また、それによって新たに操作を行わなければならない要素は生じない。
よってpi=iとなるiの個数だけ操作を行えば良い。
但しpi=iかつpi+1=i+1の時はこの2つの要素を選んで操作を行うことで操作の回数を1回減らすことができる。
以上より、先頭から要素を見ていきpi=iとなるものが現れたらpi+1と操作を行うことを繰り返せば良いことが分かる。
ソースコード
マクロ等はこちら
- const int MC = 100010;
- int N;
- int p[MC];
-
- int main(){
- scanf("%d" , &N);
- repp(i,1,N+1){
- scanf("%d" , p + i);
- }
- int ans = 0;
- repp(i,1,N+1){
- if(p[i] == i){
- ++ans;
- ++i;
- }
- }
- printf("%d\n" , ans);
- return 0;
- }
解法まとめ
先頭から要素を見ていきpi=iとなるものが現れたらpi+1と操作を行う。(10-17行)