<span>Atcoder(134)E - Sequence Decomposing</span>

Problem Statement

You are given a sequence with <var>$\mathrm{NN}$</var> integers: <var>$\mathrm{A=\{A1,A2,\cdots ,AN\}A=\{A1,A2,\cdots ,AN\}}$</var>. For each of these <var>$\mathrm{NN}$</var> integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

• If <var>${\mathrm{AiAi}}^{}$</var> and <var>${\mathrm{AjAj}}^{}$</var> <var>$(i<j)(i<j)$</var> are painted with the same color, <var>${\mathrm{Ai<AjAi<Aj}}^{}$</var>.

Find the minimum number of colors required to satisfy the condition.

Constraints

• <var>$\mathrm{1\le N\le 1051\le N\le 105}$</var>
• <var>$\mathrm{0\le Ai\le 1090\le Ai\le 109}$</var>

Sample Input 1 Copy

5
2
1
4
5
3

Sample Output 1 Copy

2

We can satisfy the condition with two colors by, for example, painting <var>$22$</var> and <var>$33$</var> red and painting <var>$11$</var>, <var>$44$</var>, and <var>$55$</var> blue.

Sample Input 2 Copy

4
0
0
0
0

Sample Output 2 Copy

4

We have to paint all the integers with distinct colors.

题意：给定一个数字串，按照从前往后从小到大进行组合，最少能组合成几条这样的数字串。

利用STL进行模拟

数据范围是1e5，时间是2s，则算法需要nlgn

通过二分法进行查找，和for遍历一遍

算法1：

将数字串全部✖-1，进行反转，转化成从前往后从大到小进行组合；

通过vector数组进行模拟，利用upper_bound（）进行查找在其前边比其 大的值进行替换为本值，没有比其大的值就push_back（）此值，拿此值作为另一串的开头。

//lower_bound()和upper_bound()的区别

时间复杂度都是lgn

lower_bound(a.begin(),a,end(),key) 是查找大于等于key的位置

upper_bound(a.begin(),a.end(),key)是查找大于key 的位置

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int main ()
{
    int n;
    cin>>n;
    int a;
    vector<int>b;
    while(n--)
    {
        cin>>a;
        a*=-1;
        int it=upper_bound(b.begin(),b.end(),a)-b.begin();
        if(it==b.size())
        {
            b.push_back(a);
        }
        else
            b[it]=a;

    }
    cout<<b.size()<<endl;
    return 0;
}

算法2：利用deque//双端队列（速度非常快）

#include<iostream>
#include<deque>
using namespace std;

int main ()
{
    int n;
    cin>>n;
    int a;
    deque<int>b;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        int it= lower_bound(b.begin(),b.end(),a)-b.begin();
        if(!it)
            b.push_front(a);
        else
            b[it-1]=a;
    }
    cout<<b.size()<<endl;

    return 0;
}