SP10620题解
#题解 2025-02-04

一道基础的贪心思想题目

此题难点并不在代码构造，而在于思想。

根据题意，已知：这 本书的编号为 到 ，且无序。

根据题目的排序方式，每一次将其中一本抽出并排到最上面(注意理解这个最上面，此上面非彼上面)。

思路：

倒着遍历数组，且把答案预设为 ，如果当前的元素与答案相等，那么则说明这个位置已经拍好，将 然后继续排序，反之当前元素应该拿到最上面去。

这么做的时间复杂度为 ，可以轻松过。

AC Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int a[300005], n, ans;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    ans=n;//预设ans=n
    for(int i = n; i >= 1; --i){ //注意是倒着遍历
        if(ans == a[i]){
            ans--;//贪心，推导如上
        }
    }
    cout << ans << endl;//输出即可
    return 0;
}