[AtCoder] ABC 135 B – 0 or 1 Swap

2019年8月4日

問題

方針

元の配列と昇順に整列させた配列を比べて、異なる箇所が \( 2 \) 箇所以下であれば、昇順にすることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  int p[N];
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> p[i];
    a[i] = p[i];
  }
  sort(a.begin(), a.end());
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a[i] != p[i]) cnt++;
  }
  if (cnt <= 2) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
  return 0;
}

感想

最初は全探索で解きましたが、整列させてから調べた方が効率的だと思いました。