首页 > 代码库 > UVa11134 Fabled Rooks (问题分解+贪心)
UVa11134 Fabled Rooks (问题分解+贪心)
链接：http://vjudge.net/problem/34086
分析：两个车相互攻击的条件是出于同一行或者同一列，因此不相互攻击的条件就是不在同一行，也不在同一列。可以看出：行和列是无关的，因此可以把原题分解成两个一维问题。把行区间和列区间拆开，用一个index变量记录行区间和列区间属于哪一个车的进行编号，假设车的行区间为[a,b]，将所有行区间按b的值从小到大排序，用贪心的思想，从排好序的第一个区间开始，优先放在行序号小的位置，列区间的处理方法与上述行的处理方法相同。最后按编号将行和列的坐标重新组合输出。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Interval { 7 int index; 8 int begin; 9 int end;10 bool operator < (const Interval& b) const {11 return end < b.end;12 }13 };14 15 const int maxn = 5000 + 5;16 17 int n;18 Interval x[maxn], y[maxn];19 pair<int, int> result[maxn];20 int vis[maxn];21 22 int main() {23 while (cin >> n && n) {24 for (int i = 0; i < n; i++) {25 x[i].index = i;26 y[i].index = i;27 cin >> x[i].begin;28 cin >> y[i].begin;29 cin >> x[i].end;30 cin >> y[i].end;31 }32 sort(x, x + n);33 bool ok = true;34 memset(vis, 0, sizeof(vis));35 for (int i = 0; i < n; i++) {36 int j;37 for (j = x[i].begin; j <= x[i].end; j++) {38 if (!vis[j]) {39 vis[j] = 1;40 result[x[i].index].first = j;41 break;42 }43 }44 if (j > x[i].end) {45 ok = false;46 break;47 }48 }49 if (ok) {50 sort(y, y + n);51 memset(vis, 0, sizeof(vis));52 for (int i = 0; i < n; i++) {53 int j;54 for (j = y[i].begin; j <= y[i].end; j++) {55 if (!vis[j]) {56 vis[j] = 1;57 result[y[i].index].second = j;58 break;59 }60 }61 if (j > y[i].end) {62 ok = false;63 break;64 }65 }66 }67 if (!ok) cout << "IMPOSSIBLE" << endl;68 else for (int i = 0; i < n; i++) cout << result[i].first << " " << result[i].second << endl;69 }70 return 0;71 }
UVa11134 Fabled Rooks (问题分解+贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。