UVa 11134 - Fabled Rooks 优先队列,贪心 难度: 0

时间:2022-03-31 16:44:56

题目

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2075

题意

n皇后类似的n(n<=5000)车,每个车所在的行列上不能有其它车,n*n棋盘放n个车。

现在约束第i个车只能放在[xli, xri], [yli, yri]这样的一个矩形中。

求放的方式。

思路

明显,行列等价且可以分开考虑。题目转化为有n线段,在每个线段内取一点,n点不相同。

由于n比较大,所以一定存在某种贪心方法。

从左向右看,则n条线段相当于n个任务,左边起点为最早时间,右边终点为最晚时间。

那么对于第i分钟,应该优先解决已经开始但没有解决的,终点最接近的任务。

感想:

一开始想的十分复杂,忘了这个问题是在一定区间内

代码