CodeForces_1348EF – Phoenix and Memory 贪心+线段树找区间最小值

这题如果没有输出2个解就很简单。 是个之前做过的类型: 把所有限制按R排序, 然后每次取出R最小的,然后从其L开始选,尽量选能选的中最小的。 这样选如果能选完,就说明有解。 贪心正确性显然:R大的至少可以选则R做为点来用。所以按R升序遍历,每次优先选左边的,能让后边的可选的更多。 用set维护可选的数即可。 这题加了个输出2个方案。 我们考虑最简单的情况:即确定一个序列后,是否有2个位置,posi,posj,使得i,j可以交换。 显然必须满足 Lj<=posi<posj<Ri 我们枚举i,只需要找到任意一个j满足上式,就可以交换i,j然后输出。 我们可以先把所有的Lj存