Description

 

Input

Output

 

Sample Input

Sample1:31 2 3Sample2:91 3 2 4 8 6 9 5 7

Sample Output

Sample1:3Sample2:5

 

Data Constraint

 

 

题解

• 题目要求的是最小的轨道数，那么肯定一条轨道停多几列要比新开一条轨道要优
• 那么只有后进来的列车x要比之前在轨道的最后一列列车的编号要小才能停
• 显然，每次要找到比x大的最小值对吧
• 然后，就可以用set来维护每个铁轨最后一列列车的编号

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 set
        
         Q; 6 int n,x; 7 int main() 8 { 9     scanf("%d%d",&n,&x); Q.insert(x);10     for(int i=2;i<=n;i++)11     {12         scanf("%d",&x);13         if (x<*Q.rbegin()) Q.erase(*(Q.upper_bound(x)));14         Q.insert(x);15     }16     printf("%d",Q.size());17     return 0;18 }