牛客 QQ11 小Q的排序

Tag: 牛客腾讯题库 Posted on 2022-03-05 09:43:10 Edited on 2022-03-05 09:43:10 Views: 148

概述

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

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