天梯题集——列车调度（模拟、二分）

r囧r小猫 2022-12-24 00:50 129阅读 0赞

### [列车调度][Link 1] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

--------------------

#### 题意 ####

这道题题意容易混淆，认为一条轨道只能停留一辆火车，其实不然，**题目中每条轨道都可排列无数辆递减的火车。**

#### 关键点： ####

①、按入口顺序排列火车  
②、排列的每条轨道火车序号必须单调递减，否则增加新轨道  
按样例来说（圆形编号为轨道编号，数字编号为火车编号）  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

有了以上的认识，问题就简单了。

#### 解题思路 ####

**①、维护轨道数组**  
维护一个轨道数组，代表每条轨道的末端火车序号。

**②、维护规则**  
若当前要添加的火车序号大于每条轨道的末端火车编号，那么就开辟一条新的轨道放置当前要添加的火车。

题目要求是最少条轨道数，我们必须从第一条轨道遍历到最后一条轨道，若存在则直接将当前轨道的最小编号替换为当前要添加的火车编号，完成添加，否则开辟新的轨道。

**③、二分优化**  
按照维护规则的逻辑，我们能够发现轨道与轨道之间的末端火车编号其实是单调递增的。为了提高效率，我们可以通过 二分法 来寻找大于当前要添加的火车编号的最小轨道编号。

**④、输出最终得到的最小轨道数**

#include<bits/stdc++.h>
    using namespace std;
    int gd[100010], arr[100010];
    int main(){ 
    	int n;
    	cin>>n;
    	for(int i=0; i<n; i++)
    		cin>>arr[i];
    		
    	int cnt=0;
    	gd[cnt++]=arr[0];
    	for(int i=1; i<n; i++){ 
    		int flag=0;
    		int l=0, r=cnt-1;
    		while(l<r){ 
    			int mid = (l+r)/2;
    			if(gd[mid]>arr[i])
    				r = mid;
    			else
    				l = mid+1;
    		}
    		if(gd[l]<arr[i])
    			gd[cnt++] = arr[i];
    		else
    			gd[l] = arr[i];
    	}
    	cout<<cnt<<endl;
    	return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805046380707840/problems/994805063166312448
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d28f81edb8bb42f9b93f8df085fd6fc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5192e636da3a4c9fb3bc99227571aad9.png