E.Correct Placement codeforces problem -1472E #693 (思维，结构体，排序)

E. Correct Placement

https://codeforces.com/problemset/problem/1472/E

思路：

• 首先，题目中的两个条件可以结合为一个条件，即大的和大的比小的和小的比。
  输入h和w时如果h<w 可以swap(h,w)，总之就是把大的当成h，小的当成w。这样可以只判断一个条件。
• 创建一个结构体，包含可以放在前面的人的编号（即答案），下标，h和w。按h从小到大升序排序，如果h相同按w从大到小降序排序（后面有注释为什么）。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
#define pii pair<int,int>
#define endl "\n"
struct node
{
	int loc, front;
	pii hw;
}a[maxn];
bool cmp1(node a, node b)
{
	if (a.hw.first != b.hw.first) return a.hw.first < b.hw.first;
	else return a.hw.second > b.hw.second;
} //按h从小到大升序排序，如果h相同按w从大到小降序排序
bool cmp2(node a, node b)
{
	return a.loc < b.loc;
}
//用于恢复数组顺序 便于输出。
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			int h, w;
			cin >> h >> w;
			if (h < w) swap(h, w);
			a[i].hw.first = h, a[i].hw.second = w, a[i].loc = i, a[i].front = -1; 
			//前面的人默认为-1（即没有）
		}
		sort(a + 1, a + 1 + n, cmp1);
		int minw = 1; //维护w最小值，初始设置为第一个人
		//这里因为h升序，对于需要寻找前面的人的这个人来说，前面的人的h必须小于他的h
		//所以第一个人的前面一定是不能有人的。
		for (int i = 2; i <= n; i++)
		{
			if (a[i].hw.second > a[minw].hw.second) a[i].front = a[minw].loc;
			//如果同时满足w也比当前查找的人更小，则找到了可以放在前面的人
			else minw = i;
			//更新最小w的值，每次查找的人只需要和前面的w最小值比较就可以，因为h已经不需要比较了
			//这里就体现了w降序的作用，这里默认了查找人的前一个人的h一定是比查找人的h小，但实际可能会有相同的情况
			//如果w降序，那查找人的前面的人如果h和他相同，w就会比他大，则不可以放在他前面。
		}
		sort(a + 1, a + 1 + n, cmp2); //恢复排序
		for (int i = 1; i <= n; i++)
		{
			cout << a[i].front << " ";
		}
		cout << endl;
	}
	return 0;
}

借鉴：https://blog.csdn.net/qq_33957603/article/details/113921247