将有序对以 a_i 为第一关键字, b_i 为第二关键字从小到大排序,变成这个样子:
显然由贪心可以知道, b_i 应该单调递减,并且很容易知道最后一个有序对一定要保留.因此只需要从后往前遍历,舍弃掉破坏 b_i 单调性的有序对(等效于把无需舍弃的有序对加入新的数组,省时),变成这个样子:
由贪心可以知道,如果选择了 a_i ,那么就可以无代价地选择之后的所有 a_i ,此时只需要选择上一个 b_i ,就组成目前最优解.( b_i 相反)
相当于,比较每一个这种组合,不断更新得到最终答案:
需要注意的是,若选择第一个 a_i 或选择最后一个 b_i ,就无需再加上另一边的值(都选择这一边的一定最优).
当且仅当 a_i \leqq c_j && b_i \leqq d_j 时探照灯可以照到海盗,若没有探照灯可以看到海盗,则说明海盗是安全的.
++cur;
现想得到一个 n 个音符的旋律 b_1b_2...b_n ,并且想让它弹奏最容易.弹奏的品的最大序号与最小序号越小,弹奏越容易.
求出可能的最小值.
可以选择其中一个六元组固定下来(例如可以固定 v[1][] ),对于这组的每一个 v[1][k] ,都把其余各组中最大的 \geqq v[i][j] 的数和最小的 \leqq v[i][j] 的数找出来,分别求它们与 v[1][k] 的差(正数)(若没有满足某个条件的数,记对应的差为 inf ).得到的就是第一个音符选择第 k 根弦,剩下的音符与其的品的差值.然后就转换成这个模型.这样我们算出了选固定组每一根弦时的最小极差,对六根弦的情况取一个最小值即可.