数据结构算法-找出矩形b不覆盖a
程序员文章站
2022-06-24 09:45:39
https://codeforces.com/contest/1472/problem/E题意:有好多个矩形,已知它们的长a和宽b和出现顺序。对于每个矩形A,寻找任意一个矩形B,使得A能放在B上且不盖住B(即Aa
https://codeforces.com/contest/1472/problem/E
题意:有好多个矩形,已知它们的长a和宽b和出现顺序。对于每个矩形A,寻找任意一个矩形B,使得A能放在B上且不盖住B(即Aa<Ba&&Ab<Bb||Aa<Bb&&Ab<Ba),找不到就输出-1。
首先要注意时找到任意一个矩形即可。我们先定义a为较大值,b为较小值,这样就只需要判断Aa<Ba&&Ab<Bb。然后我们以a为升序排列数组,这样就能保证对于每个矩形i,i-1的a<=i的a。
之后就是关键。上述的操作使我们不用考虑a的大小,所以只需要不断更新一个min为出现过的i中最小的b,来判断i的b是否大于min,满足就选择min所指的i,不满足就输出-1,然后更新min为i的b。
但是这样会带来个问题,例如 1 3 ,2 3, 2 4 ,2 5,我们会在i=2时更新min为3,这样会使i=3,i=4的时候找不到答案,输出-1。
怎么解决嘞?我们让a相同的时候b为降序排序就行。这样就是1 3,2 5,2 4,2 3,此时就不会产生上述问题辣。
(这里要注意我们对数组排序后元素的原来出现顺序就被打乱了,所以在更新了每个元素对应的答案之后要重新排序回来)
#include <bits/stdc++.h>
using namespace std;
#define qc std::ios::sync_with_stdio(0);
struct bag {
long long a;
long long b;
int num;
int ans;
};
struct bag a[200001];
bool cmp(bag a, bag b) {
if (a.a == b.a)
return a.b > b.b; //防止1 3, 2 3, 2 4,第三个元素找不到答案的情况
else
return a.a < b.a;
}
bool cmp2(bag a, bag b) {
return a.num < b.num;
}
int main() {
qc;
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].a >> a[i].b ;
//定义a为较大值,b为较小值
long long maxa = max(a[i].a, a[i].b);
long long minb = min(a[i].a, a[i].b);
a[i].a = maxa;
a[i].b = minb;
//初始化每个元素的答案为-1
a[i].ans = -1;
//给元素按顺序编号
a[i].num = i + 1;
}
sort(a, a + n, cmp);//a升序排列
int miner = 0;
for (int i = 1; i < n; i++) {
if (a[i].b > a[miner].b) {
a[i].ans = a[miner].num;
}
if (a[i].b < a[miner].b) {
miner = i; //更新miner
}
}
sort(a, a + n, cmp2); //恢复原来的排列
for (int i = 0; i < n; i++) {
cout << a[i].ans << " ";
}
cout << endl;
}
}
本文地址:https://blog.csdn.net/m0_52179369/article/details/112252213
上一篇: Bash脚本中括号和反引号的使用
下一篇: postgresql运维之远程迁移操作