想问一下一种解法的正确性(变量有点多请谅解)
查看原帖
想问一下一种解法的正确性(变量有点多请谅解)
440534
94KN楼主2021/10/27 17:43
就是一个关于有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]递推一遍就好了
2021/10/27 17:43
加载中...