列车调度

佚名 6年前 (2019-04-10) 随笔 1923人围观抢沙发百度已收录

https://pintia.cn/problem-sets/994805046380707840/problems/994805063166312448

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

第i辆开进站的车厢应该排在k个队列中的哪一条队列？

贪心，应排在 队列最后的车的序列号比第i辆进站车厢序列号In[i] 大 且 两车厢序列号差值最小 的队列
如果所有已开的用于缓冲的队列都差不进去，那么新开一条用于缓冲的队列

对每次开进站的车厢进行上述操作后，判定至少还有一条空的队列

那么，如何找到最小的k呢？

一开始我想的是二分+判定，判定函数真的开了1e5个队列，结果爆内存，

后来我想到如果使用静态链表，只需要1e5个node节点就可以了，结果超时

（写这篇总结的时候我想到，为什么要二分判定呢，为什么不直接 init k=1; for(int i=0;i<n;i++){进行1.2. ; 如果当前k条队列都成缓冲队了就k++} 呢，这样的话读一次输入数据就得到答案了呀，其实这种做法不就是题解中的做法吗（除了下文提到的我的会采取能出站的就出站的策略这一点之外））

之后看了题解，我发现实际上题解中“模拟”，和我的模拟的区别之处在于，网上所有题解的模拟对应到现实情形中是这样的：

　　所有开进站的车，正确进站之后即使它可以开出站了但是其实并没有立即开走，换句话说，模拟走完后，所有车厢是都停在车站的

　　而我的模拟是只要有一个可以出站的车厢，我会立即让它出站，我之所以这么模拟是考虑到，这样的例子，一个队列存了87（队列尾）···（队列头），然后序列号为9的车厢进站了，按我的模拟它出站了，这时发现这条的这两个等着的车厢可以立即出站了，为什么不出呢，出了有多了一条空队列啊！多好啊！

实际中我的模拟的完整过程

　　判定进站的能不能立即出站
　　能，出，判定缓冲状态的能不能出，递归把能出站的出完
　　不能，进行1.2.

所以我肯定会怀疑你能出站的没出站的这种模拟是不是有问题的，但是其实这种模拟是没问题的，但是我解释不清楚，就跟我解释不清楚贪心的正确性一样，所以我没解释贪心正确性，也许可以理解成这种不出站其实相当于所有通过此队列的车厢都会被此队列记录下来，这样最后完整的记录结果和不出站的模拟其实是一样的）

下面贴一下代码解释

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int> S;//由于不需要模拟出站的操作，只记录每个缓冲队列最后一个车厢的序列号用于1.就足够了
　　　　　　　　　//S中的每一个元素，代表一条缓冲队列的最后车厢的序列号

    int n;
    cin>>n;
    int t;
    while(n--){
        cin>>t;
        if(S.upper_bound(t)!=S.end())　　　　　　//如果能插入已存在的缓冲队，只需替换（也就是一次erase一次insert）， 否则新增个缓冲队（也就是只有一个insert）
            S.erase(*S.upper_bound(t));
        S.insert(t);
    }
    cout<<S.size()<<endl;
    return 0;
} 
//O(NlogN)