CF2200B Deletion Sort

cjz1234 · 2026-03-05 17:23:29 · 题解

问题概述

给定一个数组，每次可以删除任意一个元素，目标是让数组变成非递减，求最后最少能剩下多少个元素。

思路

这道题的关键在于：只要原数组不是非递减的，我们总能删到只剩 1 个元素。

证明

• 如果数组已经是非递减的，即不能删除任何元素，则答案是 n。
• 如果数组不是非递减的，即我们可以不断删除"破坏"非递减性质的元素，直到只剩 1 个元素。
• 任何单个元素的数组都是非递减的，因为没有相邻元素需要比较。

AC Code

#include<bits/stdc++.h>

using namespace std;
const int N=15;
int a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        bool f=0;
        for(int i=1;i<n;i++){
            if(a[i]>a[i+1]){
                f=1;
                break;
            }
        }
        if(!f){
            cout<<n<<endl;
            continue;
        }
        cout<<1<<endl;

    }

    return 0;
}

管理员大大求过。