Impressing the Boss | HourRank 27
左から要素を見ていく。 a[i] > a[i+1]であるような隣接する2つの要素を見つけた場合、対処は2種類ある。
(1) a[i]の値を小さくする。
これができるのは i = 0の場合、もしくはi>0かつa[i-1]<=a[i+1] の場合のみ
(2) a[i+1]の値を大きくする。
具体的にはa[i+1]=a[i]とする。
(1), (2)の操作が両方可能な場合は(1)の操作を優先する。というのは、a[i+1]の値が小さい方が j>=i+2 以降で条件を満たしやすくなるため。
操作回数が1回以下であればYES、それより多ければNO。
int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); int T; cin >> T; while (T--) { int N; cin >> N; vi A(N); rep(i, N)cin >> A[i]; int cnt = 0; FOR(i, 1, N) { if (A[i - 1] > A[i]) { if ((i - 2 >= 0 && A[i - 2] <= A[i]) || i == 1); else A[i] = A[i - 1]; cnt++; } } if (cnt > 1)cout << "NO" << endl; else cout << "YES" << endl; } }