题解：CF2200B Deletion Sort

NEKO_Daze · 2026-03-07 20:58:07 · 题解

洛谷CF2200B || CodeForces 2200 B

简要题意

进行 t 次操作。每次对一个长度为 n 的数组进行删除某些单项，直至剩余元素组成递减数列为止。输出最小化的数组剩余元素个数。

思路

如果拿到的数组已经是递减的了，那答案显然是 n。

否则，一定 \exist i\in[1,n]，使得 a_i<a_{i+1}，我们只需要删除剩下的元素，再删除二者之中的一个，这样就只剩下最后一个元素，答案为 1。

因此如果输入数组非递减，答案一定为 1。

评测记录

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int> a(n);
        for (auto &i : a) cin >> i;
        if (is_sorted(a.begin(), a.end())) cout << n << '\n';
        else cout << "1\n";
    }
}