题目传送门
https://vjudge.net/problem/UVA-11134
题意
在一个n×n的国际象棋棋盘中，有n个国际象棋中的车，然后题目会给出n块区域，要求这n个车既要在这n个区域中，又要使车不能互相吃（两两不在同一行或不在同一列）。
分析（建议先去看我前面的博客“贪心与区间问题”再来攻克此题）
这道题非常像回溯法的n皇后问题，但是仔细一想你就会发现事情不对。
假设它个你的区域非常大怎么办，难道你要把所有的区域每个格子都dfs一遍，况且n皇后问题顶多也就8行8列，这玩意儿给你个最大值5000！必定超时！所以立即推——>放弃回溯。
那怎么做呢?其实最关键的就在于行和列互不相等，我们能不能把行和列分解成两个子问题来解答呢？答案是可以的，我们完全可以分两步，第一步算出符合条件的所有行坐标，第二步再算出所有符合条件的列坐标，然后我们就可以将两个坐标合并得到答案了。
是不是很神奇，请诸位仔细思考这个分解的过程。这样我们就把一个二维的问题分解成了两个一维的问题了，仔细想想接下来的问题是不是跟前面“贪心与区间问题”这篇文章里差不多呢，希望大家自己思考一下。
然后我们来讲一下分解后的每一步该怎么求呢，这就要用到贪心算法，还记得我们的贪心与区间问题吗，这里也就是借鉴了那里其中一道题目的创意。就是我们把所有的区间按照右端点从小到大排序，然后我们在尽量把车往区间的左边放，如果整个区间都放不下了，那就输出“impossible”
代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int,int> P;
struct pos{
int left,right,num;
};
int vis[5000];
int main(){
int n;
while(cin>>n&&n){
pos* a=new pos[n+10];
pos* b=new pos[n+10];
P* ans=new P[n+10];
memset(vis,0, sizeof(vis));
for(int i=0;i<n;i++) {
cin >> a[i].left >> b[i].left >> a[i].right >> b[i].right;
a[i].num=b[i].num=i;
}
sort(a,a+n,[](pos A,pos B){ return A.right<B.right;});
sort(b,b+n,[](pos A,pos B){ return A.right<B.right;});
int flag=1;
for(int i=0;i<n&&flag;i++){
int t=a[i].left;
while(vis[t])
t++;
if(t<=a[i].right){
vis[t]=1;
ans[a[i].num].first=t;
}
else
flag=0;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<n&&flag;i++){
int t=b[i].left;
while(vis[t])
t++;
if(t<=b[i].right){
vis[t]=1;
ans[b[i].num].second=t;
}
else
flag=0;
}
if(!flag)
cout << "IMPOSSIBLE" << endl;
else{
for(int i=0;i<n;i++)
cout << ans[i].first << ' ' << ans[i].second << endl;
}
}
return 0;
}
|