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