Codeforces Round 857 (Div. 2) ——D题

题目链接：
https://codeforces.com/contest/1802/problem/D

  这题补题花了好长时间。结果发现题意没理解清。我们设第一个朋友为 $A$，第二个朋友为 $B$，那个每个商店中第一个物品 $a[i]$ 只能买给 $A$，第二个物品 $b[i]$ 只能买给 $B$。

大概题意：
  要给 $A$，$B$ 两个朋友买礼物，有 $n$ 个店铺，每个店铺有两种商品 $a$, $b$，其中第 $i$ 个店铺中的 $a[i]$ 只能买个朋友 $A$，$b[i]$ 只能买给朋友 $B$，且每个店铺必须且只能买一样（两件商品是互斥的）。问买给 $A$ 的商品的最大价格与买给 $B$ 的商品的最大价格的差值最小为多少？

思路：

  将商店的商品用pair对存储，然后根据 $a[i]$ 排序，我们就可以开始讨论了。

  假设买给 $A$ 的礼物最大价格为 $a[i]$，那么此时大于 $i$ 的部分和小于 $i$ 的部分其实情况是不同的。对于大于 $i$ 的部分，每个商店必须选 $b[j]$（否则就与假设矛盾），因此我们就需要统计出来 $b[j]$ 中的最大值作为买给 $B$ 的最大价格 $bmax$。

• 如果 $bmax \ge x$，那么我们不用考虑 $j \lt i$ 的情况了，因为前面即使存在大于 $bmax$ 的 $b[j]$，我们也不要选，因为会使得两人的价格差变得更大，而更小的 $b[j]$ 则不会影响最终的 $bmax$。
• 如果 $bmax \lt x$，那么我们就还需要考虑一下 $j \lt i$ 的部分中是否存在与 $x$ 的差值更小的 $b[j]$，在前半段中不管 $b[j]$ 是大于 $x$ 还是小于 $x$，都有可能使得差值更小，我们可以用二分来寻找最接近 $x$ 的 $b[j]$ 值，并且比较差值。

  对于上述操作，可以用multiset来维护，multiset默认从小到大排序，且自带二分函数。由于我们需要分别对 $j > i$ 的部分和 $j < i$ 的部分进行操作，所以我们可以用两个multiset来进行维护。随着for循环的进行，后半段每次erase一个元素，前半段每次insert一个元素即可。

  multiset操作yyds，啥时候才能灵活使用啊呜呜呜~

AC代码：

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 500010, INF = 0x3f3f3f3f;
PII a[N];
int n;
int ans;

void solve(){	
	scanf("%d", &n);
	multiset<int> ms1, ms2;  //ms1: 前半段，ms2:后半段 
	for(int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].x, &a[i].y);
		ms2.insert(a[i].y);
	}
	sort(a, a + n);
	ans = INF;
	for(int i = 0; i < n; i++){
		int x = a[i].x, y = a[i].y;
		ms2.erase(ms2.find(y));  //互斥选项，i选了a[i]后, 就不能选b[i]了
		if(ms2.size()){ //最后一个erase会导致ms2为空 
			//后半段的情况 
			auto it = ms2.end();
			it--;
			int mx = *it;  //i后面b[j]的最大值 (j > i)
			if(mx >= x) ans = min(ans, mx - x);
			else{
				ans = min(ans, x - mx);
				//需要考虑下前半段, 找到和x差值最小的那个b[k] 
				auto it = ms1.lower_bound(x);
				if(it != ms1.end()) ans = min(ans, *it - x);
				if(it != ms1.begin()) {
					it--;
					ans = min(ans, x - *it);
				}
			}
		}
		else{
			//只需要考虑前半段即可 
			auto it = ms1.lower_bound(x);
			if(it != ms1.end()) ans = min(ans, *it - x);
			if(it != ms1.begin()) {
				it--;
				ans = min(ans, x - *it);
			}
		}
		ms1.insert(y);
	}
	printf("%d\n", ans);
}

int main(){
	int T = 1;
	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}