语言漩涡

thirtiseven 的博客

0%

POI3 Rooks 思维

Posted on Edited on

题意

在一个 n*n 的棋盘上放置 n 个象棋中的车（只能横着走或者竖着走），每个车只能放置在棋盘中一个给定的矩形区域内部，求一种放置方案使这n个车互不攻击，或者声明这样的方案并不存在。

输入输出

一个 n，.

n 行，每行两个坐标，表示第 i 个车只能放置在这两个坐标限定的矩形区域内。

如果方案存在，输出 n 行，每行一个坐标，表示第 i 个车的位置。如果不存在，输出 "NIE"

样例

1
2
3
4
5
4
1 1 1 1
1 3 2 4
3 1 4 2
2 2 4 4
1
2
3
4
1 1
2 3
3 2
4 4

解法

车的攻击模式是正交的（是这么说的吗），它在哪一行和它要攻击哪一列的目标是无关的，所以我们可以将原题拆分为两个一维的问题，分别独立考虑：

长度为n的线段，有n个区间，求一个n-排列，使数字 i 恰好落入第 i 个区间中。

这个题怎么做呢，很简单，我们反过来考虑这样一个做法：对第 i 个数字，安全地选择一个区间和它配对。执行 n 次这个操作，就做完了。什么是“安全地选择”，就是要让它对后续操作的影响最少。显然，最安全的选择就是选择一个包含第 i 个数字，且右端点最靠左的区间。

于是我们就可以得出一个这样的算法：从左到右，找到包含第 i 个数字的还没配对的区间中右端点最靠左的那个，然后把这个区间从还没配对的区间集合里删掉。如果一个这样的区间都找不到，说明无解。我们需要三个操作：插入一个区间，查询右端点最小的区间，删除一个右端点最小的区间。所以可以用一个优先队列来维护。

然后就做完了，复杂度是 O(nlogn).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

const int maxn = 3005;

struct interval{
	int x, y;
	int id;
	int place;
	bool operator<(const interval& that) const {
		if (y == that.y) {
			return id > that.id;
		}
		return y > that.y;
	}
};

bool cmp_by_x(interval alice, interval bob) {
	if (alice.x == bob.x) {
		return alice.id < bob.id;
	}
	return alice.x < bob.x;
}

bool cmp_by_id(interval alice, interval bob) {
	return alice.id < bob.id;
}

int n;
interval a[maxn], b[maxn];
std::priority_queue<interval> aa, bb;
std::vector<interval> ansa, ansb;

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	std::cin >> n;
	bool yes = 1;
	for (int i = 0; i < n; i++) {
		std::cin >> a[i].x >> b[i].x >> a[i].y >> b[i].y;
		a[i].id = b[i].id = i;
		if (a[i].x > a[i].y || b[i].x > b[i].y) {
			yes = 0;
		}
	}
	std::sort(a, a+n, cmp_by_x);
	std::sort(b, b+n, cmp_by_x);
	int cnta = 0, cntb = 0;
	for (int i = 1; i <= n; i++) {
		while (cnta < n && a[cnta].x <= i) {
			aa.push(a[cnta]);
			cnta++;
		}
		while (cntb < n && b[cntb].x <= i) {
			bb.push(b[cntb]);
			cntb++;
		}
		if (aa.size() <= 0 || bb.size() <= 0) {
			yes = 0;
			break;
		}
		ansa.push_back(aa.top());
		ansa[i-1].place = i;
		if (ansa[i-1].y < i) {
			yes = 0;
			break;
		}
		aa.pop();
		ansb.push_back(bb.top());
		ansb[i-1].place = i;
		if (ansb[i-1].y < i) {
			yes = 0;
			break;
		}
		bb.pop();
	}
	if (yes == 0) {
		std::cout << "NIE\n";
		exit(0);
	}
	std::sort(ansa.begin(), ansa.end(), cmp_by_id);
	std::sort(ansb.begin(), ansb.end(), cmp_by_id);
	for (int i = 0; i < n; i++) {
		std::cout << ansa[i].place << ' ' << ansb[i].place << '\n';
	}
}

吐槽

差不多一个月没做题，感觉不错，朋友们我们下个月见。