PTA L2-014 列车调度 （25 分) （C++） STL

用set容器存序号 upper_bound()在容器二分查找比当前列车号大的元素若找到就删除比当前列车号大的元素 插入当前列车号 若未找到则直接插入 等同于新开一个轨道 最后统计容器的size

关于upper_bound()与lower_bound()

1. upper_bound() ：

iterator upper_bound( const key_type &key );

在当前多元集合中返回一个指向大于Key值的元素的迭代器。

从数组begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,可以找到数字在容器中的下标。

2. lower_bound() :

iterator lower_bound( const key_type &key );

返回一个指向大于或者等于key值的第一个元素的迭代器。

从数组begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

//此处语法参考 https://blog.csdn.net/qq_40160605/article/details/80150252

题解如下

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
	set<int> s;
	int n,num;
	cin >> n;
	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();
}