数据结构算法-找出矩形b不覆盖a

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