【2020HBU天梯賽訓練】7-40 列車排程

7-40 列車排程

火車站的列車排程鐵軌的結構如下圖所示。

兩端分别是一條入口（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           

複制

set奇解 set自動排序 直接定位

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num,n;
    cin>>n;
    set<int> s;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(s.upper_bound(num)!=s.end())
            s.erase(s.upper_bound(num));
        s.insert(num);
    }
    cout<<s.size();
    return 0;
}           

複制

用數組加sort逾時，

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>num(n);
	for(int i=0;i<n;i++)cin>>num[i];
	vector<int>ans;
	ans.push_back(num[0]);
	for(int i=1;i<n;i++){
		int flag=1;
		sort(ans.begin(),ans.end());
		for(int j=0;j<ans.size();j++){
			if(ans[j]>=num[i]){
				//cout<<"&&"<<ans[j]<<"^^"<<num[i]<<"&&"<<endl;
				ans[j]=num[i];
				flag=0;	
				break;
			}
		}if(flag){
			ans.push_back(num[i]);
			//cout<<num[i]<<"****"<<endl;	
		}
	}cout<<ans.size();
	return 0;
}            

複制