欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

数据结构算法-找出矩形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