题意

给定一个数列,问最少删除多少个数,使得数列为先严格单调递增后严格单调递减的数列.

限制:有多组数据,每组数列个数不大于3000

方法

双重循环

要删除的人最少,就是要留下的人最多,所以我们以要留下的人最多的来思考

一个严格单调递增,再严格单调递减的序列,不妨把它拆分成两部分处理.

如果我们能计算从最左开始到当前位置的单增的最大长度,那么我们仅需要把数组翻转,再次计算单增的最大长度,就可以得到它在原数组中的向结尾方向的最大单调递减的长度.

这样再枚举每个位置,可以得到以每个位置为合唱队列的峰值的最大长度.

那么问题变成了如何计算最大单增的长度

既然我们有结果数组来记录, 那么一个位置的最大长度,只需要找它前面比它小的,最大长度又尽量长的即可.

令$cnt[i]cnt[i]$ 表示从开始到$ii$的最大长度,那么有

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

vector<int> getInc(vector<int> & arr){
    vector<int> cnt(arr.size(),1); // 结果
    rep(i,0,arr.size()){
        rep(j,0,i){ // 找i前面 
            if(arr[j] < arr[i]){ // 比当前值小的
                cnt[i] = max(cnt[i],cnt[j]+1); // 且长度最大
            }
        }
    }
    return cnt;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<int> a(n,0);
        rep(i,0,n)
            scanf("%d",&a[i]);
        auto inc = getInc(a);
        reverse(a.begin(),a.end()); // 翻转 寻找单调递减
        auto dec = getInc(a);
        reverse(dec.begin(),dec.end()); // 翻转 单调递减的结果
        int del = a.size();
        rep(i,0,n){
            del = min(del,int(a.size()+1-inc[i]-dec[i])); // 总个数 - 1 - 最大左单增 - 最大右单减
        }
        printf("%d\n",del);
    }
    return 0;
}

复杂度分析

时间复杂度: 我们对于每个数列的读入,翻转,统计,输出操作都是$O(n)O(n)$的,主要考虑找打最大长度的复杂度.这一块采取了双重循环,所以总时间复杂度为 $O(n^2)O(n^2)$, 庆幸的是数据比较小,AC了.

**空间复杂度: **主要空间复杂度都在开vector上,上面所有vector的使用都与数组长度相关,所以总空间复杂度为$O(n)O(n)$

单增队列+二分搜索

先看样例数据

8
186 186 150 200 160 130 197 200

我们需要的结果数组就是从最左到每个值的最大单增长度.

在此,我们借助一个辅助数组,辅助数组中记录当前单增长度对应的最小值

这样就能计算最大的单增的长度

注意到其中辅助数组是单调递增,所以每次找位置的时候可以用二分来加快找的速度.

最后我们得到的结果数组,就是从左侧开始到对应位置的最大长度

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

vector<int> getInc(vector<int> & arr){
    vector<int> cnt(arr.size(),1); // 结果
    vector<int> inc = {}; // 辅助数组
    rep(i,0,arr.size()){
        if(inc.size() == 0 || arr[i] > inc[inc.size()-1]){ // 比最后的还大 插入到最后
            inc.push_back(arr[i]);
            cnt[i] = inc.size();
        }else{ // 二分找位置
            int idx = lower_bound(inc.begin(), inc.end(), arr[i]) - inc.begin();
            inc[idx] = arr[i];
            cnt[i] = idx+1;
        }
    }
    return cnt;
}


int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<int> a(n,0);
        rep(i,0,n)
            scanf("%d",&a[i]);
        auto inc = getInc(a);
        reverse(a.begin(),a.end()); // 翻转 寻找单调递减
        auto dec = getInc(a);
        reverse(dec.begin(),dec.end()); // 翻转 单调递减的结果
        int del = a.size();
        rep(i,0,n){
            del = min(del,int(a.size()+1-inc[i]-dec[i])); // 总个数 - 1 - 最大左单增 - 最大右单减
        }
        printf("%d\n",del);
    }
    
    
    return 0;
}

复杂度分析

时间复杂度: 我们对于每个数列的读入,翻转,统计,输出操作都是$O(n)O(n)$的,主要考虑找打最大长度的复杂度.这一块遍历了数组,维护了单增队列inc数组和二分搜索每次找位置插值,所以总时间复杂度为 $O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 主要空间复杂度都在开vector上,上面所有vector的使用都与数组长度相关,所以总空间复杂度为$O(n)O(n)$