题解 | 有序序列判断

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int pre;
    cin >> pre;

    if (n == 1) {
        cout << "sorted";
        return 0;
    }

    // --- 处理第二个数（确定初始趋势）---
    int num;
    cin >> num;

    bool greater = false, less = false, equal = false;
    if (num > pre) greater = true;
    else if (num < pre) less = true;
    else equal = true;
    pre = num;

    // --- 处理第3个及以后的数 ---
    for (int i = 2; i < n; i++) {
        cin >> num;

        if (greater) {
            if (num < pre) {
                cout << "unsorted";
                return 0;
            }
        } else if (less) {
            if (num > pre) {
                cout << "unsorted";
                return 0;
            }
        } else if (equal) {
            if (num != pre) {
                if (num > pre) greater = true;
                else if (num < pre) less = true;
            }
        }
        pre = num;
    }

    cout << "sorted";
    return 0;
}

看到了这题就想到了可以用状态机的思想来解决。

本题共有三种状态：大于、小于、等于。

（注：为了不使用数组，笔者使用了pre变量来存储前一个数，所以下文确定状态等操作，是从第二个数开始的）

所以思路拆成如下：

第一步、确定状态

就是根据第二个数和第一个数的关系，判断后续应该是大于、小于、等于。

第二步、判断当前是否符合该状态，不符合则退出

⚠️特别注意：本题是不完全递增递减。所以先大于后等于也是可以的。如递增状态，1 2 2 也是可以的。小于同理。