Gym - 100451E - 思维题

题目链接：https://vjudge.net/problem/Gym-100451F

 

解题思路：

对于每一对，将较小的放在x，大的放在y。然后将他们以x从小到大得规则放进set中。

在遍历的过程中如果有一对不满足条件，将他调换过来，因为y是大于x的，所以调换之后这一对肯定出现在后面，将调换的一对标记为1，如果当某一对标记是1且还不满足条件，说明这一对的任意一种形态都不能，那么就是无解。

满足条件的一对不用调换，因为已经满足条件了，如果再调换就会使得y变小，从而缩小后面的空间，因此不会使解更优。

#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
int n;
struct node
{
	int x,y;
	bool f;
	bool operator < (node A)const
	{
		if(x==A.x) return y > A.y;
		return 	x < A.x;
	}	
};
multiset <node> st;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		st.clear();
		int a,b,fx = -1,fy = 2e9;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a,&b);
			if(a>b) swap(a,b);
			st.insert(node{a,b,0});
		}
		bool ok = 1;
		for(auto it=st.begin();it!=st.end();)
		{
			node now = *it;
			if(now.y<=fy){
				it++,fy = now.y;
			}else{
				if(now.f){
					puts("no");
					ok = 0;
					break;
				}
				swap(now.x,now.y);
				now.f = 1;
				st.insert(now);
				st.erase(it++);
			}
		}
		if(ok){
			puts("yes");
			for(auto it:st)
			printf("%d %d\n",it.x,it.y);
		}
	} 
	return 0;
}