列车调度问题PTA

大家好，又见面了，我是你们的朋友全栈君。

7-20 列车调度 （25 分）
火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：
输入第一行给出一个整数N (2 ≤ N ≤10
​5
​​ )，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：
9
8 4 2 5 3 9 1 6 7
输出样例：
4

下面先展示 我的4个超时代码
1.

#include<cstdio>
#include<vector>
using namespace std;
int t;

int main(){
	int n,num=0;
	scanf("%d",&n);
	int i,j,t;
	vector<vector<int > > m(n+1);
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		for(j=0;j<num;j++){
			if(m[j][m[j].size() -1] >t) {
				m[j].push_back(t); 
				break;
			}
		}
		if(j==num){
			m[num].push_back(t);
			num++; 
		}
	}
	printf("%d",num);
	return 0;
	
}

2.思想大概和上面的VECTOR是一样的，感觉直接普通的数组还更方便
依旧超时

#include<cstdio>
using namespace std;
int a[100000+10];

int main(){
	int n,num=0;
	scanf("%d",&n);
	int i,j,t;
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		for(j=0;j<num;j++){
		if(a[j]>t) {
			a[j]=t;
			break;
		}
		}
		if(j==num){
			a[num]=t;
			num++;
		} 
		
	}
	printf("%d",num);
	return 0;
	
}

3.然后想到如果这个新进来的T比数组里所有的数都大，就没必要进入循环了；
进行了一点点改变》》》》依旧超时

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100000+10];

int main(){
	int n,num=0;
	scanf("%d",&n);
	int i,j,t,max=0;
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		if(max< t){
			a[num]=t;
			num++;
		}
		else for(j=0;j<num;j++){
		     if(a[j]>t) {
			 a[j]=t;
			
			 break;
		}
		}
		
		sort(a,a+num);
		max=a[num-1];
	}
	printf("%d",num);
	return 0;
	
}

4.嗯嗯，接着想到循环的存在就是为了找能够存放T的位置，这个位置的原有数要比T大所有就想到了upper—bound ,结果还是TLE ?

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100000+10];

int main(){
	int n,num=0;
	scanf("%d",&n);
	int i,j,t,max=0;
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		if(max< t){
			a[num]=t;
			num++;
		}
		else {
		int key=upper_bound(a,a+num,t)-a;
		a[key]=t;
		
		}
		
		sort(a,a+num);
		max=a[num-1];
	}
	printf("%d",num);
	return 0;
	
}

。。。。。。。。。。。。。。

下面是我的AC代码：
《其实就是把上一个代码的sort去了
然后发现这道题根本没必要用SORT ，1因为我们对比已有的最大值更大的值采取的方法是将这个数赋给a[num],num++，能排在原来数组内的数一定是一个比这个位置的原来的数小，比这个位置的前一个数大的数，，，，，，因此这个数组是递增的，于是乎
思路大概是：
1.先和最大的那个数进行比较，即a[num-1]，如果比他大则将这个数赋给a[num],num++；否则2.
2.直接利用upper—bound 函数判断插入的位置，
。。。。。。。。。

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100000+10];

int main(){
	int n,num=0;
	scanf("%d",&n);
	int i,j,t,max=0;
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		if(max< t){
			a[num]=t;
			num++;
		}
		else {
		int key=upper_bound(a,a+num,t)-a;
		a[key]=t;
		
		}
		
		
		max=a[num-1];
	}
	printf("%d",num);
	return 0;
	
}

以下思路FROM
1 s.insert(0); 首先先放一个0;
2 *s.rbegin() 表示set 的最后一个元素即最大的值； 注意小星星
3 s.erase( * (s.upper_bound(m)) ); 注意小星星
4 s.insert(m); 因为set存放有序的数所以直接insert
5 s.size() -1 记得减一哦

#include<set>
#include<cstdio>
using namespace std;
int main(){
	set<int > s;
	int n;
	scanf("%d",&n);
	int i,m;
	s.insert(0);
	for(i=0;i<n;i++){
		scanf("%d",&m);
		if(m >*s.rbegin() ){
			s.insert(m); 
		}else {
		s.erase(*(s.upper_bound(m)) );
		s.insert(m); 	
		}
	}
	printf("%d",s.size() -1);
	return 0; 
}