【BZOJ2109&2535】【NOI2010】航空管制

今天ljh神犇讲的题

是个双倍经验题?

首先把问题的两个限制改为:

  • 第一类(最早起飞时间限制):编号为\(i\)的航班起飞序号不得小于\(n-k_i+1\);
  • 第二类(相对起飞顺序限制):存在一些相对起飞顺序限制\((a, b)\),表示航班\(a\)的起飞时间必须晚于航班\(b\),即航班\(a\)的起飞序号必须大于航班\(b\)的起飞序号。

那么可以知道这个新的限制下的每个解对应原问题的一个解。

第二个问题转化为:求每个飞机的最大起飞序号。

这样一来问题就很简单了:只要不断地取除了当前询问飞机的同时满足上面两个限制的飞机,直到取不了,也就是必须要取当前询问飞机,那么得到的就是\(n-最大起飞序号+1\)。

说点什么

  Subscribe  
提醒