【题解】递减选择

题意

给你一个长度为的序列，以的第一个元素开始从左至右从序列中选出递减的序列，并将其从中删除，再重复这个过程，直到序列为空，输出每次挑选的递减序列。

题解

首先我们可以知道的是，每个递减序列的最后一个值它是递增的。例如有，可以得到

5 1
4 2
3

每一个序列的最后一个元素是递增的。若某个序列的末尾值加入时导致其不递增了，那么该值应该放到前面某个序列中去。故我们可以创建一个数组来存每个序列的最后一个值，那么每次有一个新的数，我们可以在这个数组中二分来找到他应该在的位置，那么对其进行替换，并且加入到那个序列的末尾中，若二分找不到比起大的，那么就创建一个新的序列。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N];
vector<int>q;
vector<int>ans[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    int cnt=0;
    for(int i=0; i<n; i++)
    {
        int pos=upper_bound(q.begin(),q.end(),a[i])-q.begin();
        if(pos!=q.size())
            q[pos]=a[i];
        else
            q.push_back(a[i]);
        ans[pos].push_back(a[i]);
        if(ans[pos].size() == 1)
        {
            cnt++;
        }
    }
    for(int i=0; i<cnt; i++)
    {
        for(int j=0; j<ans[i].size(); j++)
        {
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
}