Correct Placement
题意
n 个矩形 对于每个矩形可以将它横着放或者竖着放 问能否找到另一个矩形能够放在它前面并且不将其遮挡 如果有的话输出符合条件的矩形的编号 否则输出 −1
思路
首先 将所有矩形的较小值当成宽 较大值当作长 然后对宽进行升序排列 这样排在当前矩形前面的所有矩形的宽都是符合要求的 用 mi 记录 前面所有矩形 长的最小值 如果当前矩形的长大于这个最小值 说明可以在前面找到一个符合条件的矩形
但是会出现这样的一个问题 比如排序后是 1 3 2 2 2 4 2 5 对于第三个和第四个矩形输出 2 2 因为长的最小值更新到了第二个矩形 但是并不符合题意 所以 我们在按宽 递增排序的基础上 让长递减排序 就可以避免这种情况 1 3 2 5 2 4 2 3
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; int n, x, y; int ans[N]; struct Node { int w, l, idx; }node[N]; bool cmp(Node a, Node b) { if (a.w != b.w)return a.w < b.w; else return a.l > b.l; } void solve() { cin >> n; for (int i = 1; i <= n; ++i) { scanf("%d%d", &x, &y); if (x > y)swap(x, y); node[i].w = x; //宽 node[i].l = y; //长 node[i].idx = i; } sort(node + 1, node + 1 + n, cmp); int mi = node[1].l; //区间最小值 int id = node[1].idx; //最小值的下标 for (int i = 1; i <= n; ++i) { if (node[i].l <= mi) { //不符合条件 ans[node[i].idx] = -1; mi = node[i].l; id = node[i].idx; } else { ans[node[i].idx] = id; } } for (int i = 1; i <= n; ++i) { if (i == ans[i])printf("-1 "); else printf("%d ", ans[i]); } cout << endl; } int main() { int t; cin >> t; while(t--) solve(); return 0; }
