牛客 QQ11 小Q的排序

概述

https://www.nowcoder.com/practice/62a677c595fb471e832e4ed4107d3c63

分类讨论法

1. 如果最后一位不是最小值，最小值在前 n - 1 个中，则执行 1 操作是的最小值必然归位，执行 2 操作则其他所有值归位；
2. 如果最后一位是最小值，执行 2 操作使得其变为 1 操作，之后转到第一种情况。

实现的时候注意以下 cases：

1. 只有一个元素的情况；
2. 已经排好序的情况；

其实是情况 1 是情况 2 的一个特殊情况。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n; cin >> n;
    if (n == 1) return 0;
    vector<int> nums(n);
    int minValue = INT_MAX;
    int last = INT_MIN;
    bool sorted = true;
    for (int i = 0; i < n; i ++) {
        cin >> nums[i];
        if (nums[i] < last) sorted = false;
        last = nums[i];
        minValue = min(minValue, nums[i]);
    }
    if (sorted) cout << 0;
    else {
        if (nums[n-1] == minValue) {
            cout << 3;
        } else {
            cout << 2;
        }
    }
}

Links: 牛客-qq11-小q的排序

未经允许，禁止转载，本文源站链接：https://iamazing.cn/