就是一个关于有k个廊桥时能能停靠的飞机的最大数量(用g数组储存,即g[k])的计算方法,这里分为两个阶段。
第一阶段:先定义一个队列,从1个廊桥开始算起,用一个变量t来存储当前停在廊桥的飞机的离开时刻,初始值为0,然后遍历所有要停靠的飞机(已经以抵达时间为关键字从小到大排序了):
若该飞机的抵达时刻a大于k,则将飞机的离开时刻赋值b给k(表示该廊桥被该飞机占用了),g[1]++。
若a小于等于k,则将该飞机加入队列,并用n1记录队列里的飞机数量。
第二阶段:一个for循环,从2到k,赋值给变量i
(即for(int i=2;i<=k;i++)),然后判断队列是否空:
若为空,则代表i-1个廊桥就可以让所有要停靠的飞机有廊桥停靠,那么就将a数组中i到k这段区间全部赋值为a[i-1](或题目中的m1或m2)。
若不为空,则把n1赋值给n2,把n1和t赋值为0。然后用一个while循环(循环的执行条件是n2!=0):
从队列中取出队头元素并赋值给p(就是把第一架飞机拿出来赋值给p,p是一个结构体,下面称为p飞机),然后把队列中的队头元素删除,n2的值减1(表示队列中未被遍历的飞机数减1),最后判断飞机p的抵达时间是否大于t:
若大于t,则把飞机p的离开时间赋值给t,g[i]++
否则,就把飞机p重新加入队列,n1++(表示队列中以当前廊桥数量无法停靠在廊桥上的飞机的数量)
最后的答案只要用g[i]+=g[i-1]递推一遍就好了