[AtCoder] ABC 072 D – Derangement
問題
方針
\( p_i = i \) となる \( i \) に対して、\( (p_i, p_{i+1}) = (p_{i+1}, p_i)\) と交換します。このとき、\( p_{i+1} = i \) となるので、交換によるロスはありません。\( p_N = N \) のときは、\( (p_{N-1}, p_N) = (p_N, p_{N-1}) \) と交換すれば良いです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; int p[N]; for (int i = 0; i < N; i++) { cin >> p[i]; } int ans = 0; for (int i = 0; i < N - 1; i++) { if (p[i] == i + 1) { ans++; swap(p[i], p[i + 1]); } } if (p[N - 1] == N) { ans++; } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません