这是关于算法题的错题整理及反思

题目来源不一定，主要来源应该是CF、洛谷等

也会包含一些关于比赛的反思等

Codeforces Round 982 (Div. 2) B

标签：

• 暴力枚举（brute force）
• 贪心（greedy）

题目：

1. Problem-B-Codeforces
2. Stalin Sort-洛谷

题目大意

给出一个数组，问是否可以通过对其任意子数组进行多次斯大林排序，使得最终的数组是非增的。

*子数组指的是任意一段连续子数组，斯大林排序指将严格降序的元素剔除，具体定义见题目

思路分析：

通过斯大林排序的定义可知

• 任何一段数组进行斯大林排序后第一个元素都不会改变

• 如果处理完的数组元素大于等于两个，则按非降序排列

进一步分析

• 对于使用斯大林排序的任意子数组，如果存在大于第一个元素的其他元素则会被保留，而小于第一个元素的一定会被剔除
  因此要使最后是非降序的，就必须要把子数组中大于第一个元素的其他元素都剔除掉
• 那么要使剔除后的数组是可以通过对其任意子数组进行多次斯大林排序，使得最终的数组是非增的
  就要使剔除后的数组的首元素最大
• 接下来只需要从头遍历整个数组，找到有最多元素的满足首元素最大的数组（不一定连续）即可
• 即对数组中的每个元素寻找有多少个（k）在他之后的不大于他的元素，并记录下最大值（f）
• 将元素总个数减去（最大值+1）就是其他要剔除的元素的个数

可能的疑问

问题一：对每个元素只考虑后面的其他元素，为什么不用考虑前面的其他元素就把他们全部剔除

答：

• 如果前面的元素大于等于该元素，则前面元素遍历时的值k1就会大于该值k2，那么f就会等于k1，不影响
• 如果前面的元素小于该元素，则必须剔除，否则剔除后的数组的首元素就不是最大的，那么就不满足要求

思路误区：

比赛时想的是减序列通过斯大林排序一定会消失，所以先对整个数组进行一次斯大林排序，得到非减序列，再把第一次出现的最大值前的元素全部剔除掉，那么剩下的就是非增序列了，问题在于在第一次通过斯大林排序时删掉的元素仍在剔除元素后的数组之中，此时数组还可能存在递增序列，不满足题意

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t; // 读取测试用例数量  
    while (t--)
    {
        int n;
        cin >> n;
        int* a = new int[n + 1];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        int f = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int k = 0;
            for (int j = i + 1; j < n; j++)
            {
                if (a[j] <= a[i])
                    k++;
            }
            f = max(f, k);
        }
        cout << n - (f + 1) << endl;
        delete[] a;
    }
    return 0;
}