PTA:L2-014 列车调度

梦里梦外; 2024-03-17 17:04 47阅读 0赞

## 题目： ##

[PTA | 程序设计类实验辅助教学平台千名教师建设，万道高质量题目，百万用户拼题的程序设计实验辅助教学平台![apple-touch-icon.png][]https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805063166312448][PTA _ _apple-touch-icon.png_https_pintia.cn_problem-sets_994805046380707840_exam_problems_994805063166312448]

L2-014 列车调度

火车站的列车调度铁轨的结构如下图所示。

![b63cebb7d69e9a4492554e9a9a663532.png][]

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

#### 输入格式： ####

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

#### 输出格式： ####

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

#### 输入样例： ####

9
    8 4 2 5 3 9 1 6 7

#### 输出样例： ####

## 题目分析： ##

![8d8bcbbc8ec44cfa9d7eb2dd0ded045c.png][]

![bcff8a64074243d789095cb2fb128225.png][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n,cnt,mid,a[N],s[N];
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		int l=1,r=cnt;
    		while(l<r)
    		{
    			mid=(l+r)/2;
    			if(s[mid]>a[i])r=mid;
    			else l=mid+1;
    		}
    		if(s[l]>a[i])s[l]=a[i];
    		else 
    		{
    			cnt++;
    			s[cnt]=a[i];
    		}
    	}
    	cout<<cnt;
    	return 0;
    }

[apple-touch-icon.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fa9cec49345c451482c69cabcd04b3f7.png
[PTA _ _apple-touch-icon.png_https_pintia.cn_problem-sets_994805046380707840_exam_problems_994805063166312448]: https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805063166312448
[b63cebb7d69e9a4492554e9a9a663532.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0aee365ffd4c4735b1fbe36491baeb3b.png
[8d8bcbbc8ec44cfa9d7eb2dd0ded045c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bb6e1cf00df94faa936fc3ce9914e0f8.png
[bcff8a64074243d789095cb2fb128225.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a2ccd90f6f01487483ba0ef52a99d383.png