方法一 利用“归并排序求逆序对”的思想

分析本题我们可以知道，该题目是想让我们找到一个子数列，使得该子数列可以通过使用斯大林算法，可以只剩下第一个位置上的元素。问我们通过最少删减多少个元素可以获得这样的子数列。
通过分析斯大林算法和题目要求，我们只需要找到每个元素它们后面有多少比它们自己大的元素（假设有x个），再结合每个元素在原数列中的位置（假设为i，i从0开始记），那么所有元素的(x+i)值，最小的那个即为所求。
x的值可用通过两重循环遍历来计算，但一定超时，因此我们可以采用归并排序求逆序对的方法计算，从而降低时间复杂度。

代码展示

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map> 
#include<utility>
using namespace std;
const int N = 2010;
typedef pair<int, int> PII;
int t;
PII a[N], b[N];
int cnt[N];
void merge(PII a[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge(a, l, mid), merge(a, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        int i1 = a[i].first, i2 = a[i].second;
        int j1 = a[j].first, j2 = a[j].second;
        if(i1 >= j1)
        {
            b[k ++] = a[j ++];
        }
        else if(i1 < j1)//如果a[i]小于a[j],那么说明a[i]小于所有a[j+x] 
        {
            cnt[i2] += r - j + 1;
            b[k ++] = a[i ++];
        }
        //cout << 1 << endl;
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(int i = l, j = 0; i <= r; i ++, j ++) a[i] = b[j];
}
int main()
{
    cin >> t;
    //cout << t / 2 << endl;
    while(t --)
    {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(cnt, 0, sizeof cnt);
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++)
        {
            scanf("%d", &a[i].first);
            a[i].second = i;
        }
        merge(a, 0, n - 1);
        for(int i = 0; i < n; i ++)
        {
            //printf("%d ", cnt[i]);
            cnt[i] += i;
        }
        int m = 0x3f3f3f3f, idx;
        for(int i = 0; i < n; i ++)
        {
            if(m > cnt[i])
            {
                m = cnt[i];
                idx = i;
            }
        }
        printf("%d\n", m);
    }
    return 0;
}