首页 > 代码库 > UVa 11134 传说中的车

UVa 11134 传说中的车

2024-09-02 12:21:00   219人阅读

https://vjudge.net/problem/UVA-11134

题意：在n*n的棋盘上放n个车，使得任意两个车不相互攻击，且第i个车在一个给定的矩形Ri之内。用4个整数xli，yli，xri，yri来描述第i个矩形。

思路：行和列是不影响的，也就是说第i个棋子放在第几行不会影响它的列数。这样的话我们就可以分别处理行和列。由于棋子被给定了范围，这样的话我们可以用贪心法来解决，按照ri右坐标从小到大排序，然后从左坐标开始选出最小的且未被占据的坐标。

 1 #include<iostream>   2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5  6 const int maxn = 100000; 7  8 int n; 9 int ok;10 11 int vis_row[maxn];12 int vis_col[maxn];13 14 int ans_row[maxn];15 int ans_col[maxn];16 17 struct node18 {19     int l, r;20     int id;21 }x[maxn],y[maxn];22 23 bool cmp(node a, node b)24 {25     return a.r < b.r || (a.r == b.r && a.l < b.l);26 }27 28 void solve()29 {30     memset(vis_row, 0, sizeof(vis_row));31     memset(vis_col, 0, sizeof(vis_col));32     //处理行33     for (int i = 0; i < n; i++)34     {35         ok = 0;36         int num = x[i].id;37         for (int j = x[i].l; j <= x[i].r; j++)38         {39             if (!vis_row[j])40             {41                 ans_row[num] = j;42                 vis_row[j] = 1;43                 ok = 1;44                 break;45             }46         }47         if (!ok)  return;48     }49 50     //处理列51     for (int i = 0; i < n; i++)52     {53         ok = 0;54         int num = y[i].id;55         for (int j = y[i].l; j <= y[i].r; j++)56         {57             if (!vis_col[j])58             {59                 ans_col[num] = j;60                 vis_col[j] = 1;61                 ok = 1;62                 break;63             }64         }65         if (!ok)  return;66     }67 }68 69 int main()70 {72     while (cin >> n && n)73     {74         for (int i = 0; i < n; i++)75         {76             cin >> x[i].l >> y[i].l >> x[i].r >> y[i].r;77             x[i].id = i;78             y[i].id = i;79         }80         sort(x, x + n, cmp);81         sort(y, y + n, cmp);82         solve();83         if (ok)84         {85             for (int i = 0; i < n; i++)86             {87                 cout << ans_row[i] << " " << ans_col[i] << endl;88             }89         }90         else cout << "IMPOSSIBLE" << endl;91     }92 93     return 0;94 }

 

UVa 11134 传说中的车


联系
我们