团体程序设计天梯赛-练习集 - L2-014 列车调度（25 分）

团体程序设计天梯赛-练习集 - L2-014 列车调度（25 分）

解题思路：必须要车号大的先出，小的后出。所以列车排队的每一队必须是从大到小排列（从右往左看），才能保证开出去的车也是从大到小的。

对于每一个想要进入并列铁轨的车：

如果车号大于每一队的队尾的车号，说明不能进入已经有的队伍，必须进入新的铁轨；

否则，选择一个最接近它车号的尾部车号的队伍进入。

其实无需保存每一个并行队列的所有值，只需要保存当前队伍的车尾（就是每一列最左边 即 每一列的最小值）即可。

因为每一次都是需要排序比较大小的，所以用set自动排序。

首先把set里面放入一个0值。每一次set的最后一个值s.rbegin()都是当前所有队列队尾的最大值。

如果当前想要进入排队队伍的t值比集合里面最大值小，就移除第一个比他大的值，然后把t插入集合中。表示的是将t值插入了最接近它车号的队伍的队尾；

否则就直接插入进去t值。作为新的队伍。

AC 代码

#include#include#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;set st;int main(){ st.insert(0); int n,a; scanf("%d",&n); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。