本文共 1976 字，大约阅读时间需要 6 分钟。

CF1463-D. Pairs

题意：

有从\(1\)到\(2n\)一共\(2n\)个数字，让你将这\(2n\)个数字分成\(n\)组，每组有两个数字。对于这\(n\)组数字，你可以从中挑选\(x\)组做\(min\)操作，其他的\(n-x\)组中做\(max\)操作，这样就可以得到一个新的数组\(b\)； 现在题目给你得到的数组\(b\)，问你可以有多少不同的\(x\)使得可以得到数组\(b\)。

思路：

我们从这\(2n\)个数字中去掉数组\(b\)中的数，剩下的就是数组\(a\)中的数。对\(a\)，\(b\)数组排序之后，我们现在先枚举每个\(x\)让\(a\)中最大的\(x\)个数字从小到达与\(b\)中最小的x个数字从小到大组合，让\(a\)中剩余的\(n-x\)个数字从小到大与\(b\)中剩余的\(n-x\)个数字从小到大组合（类似于贪心的思想），这个应该是最优的情况，如果这样还是不能通过前\(x\)个取\(min\)后\(n-x\)取\(max\)得到数组\(b\)，那么对于这个\(x\)无论你再怎么组合都不可能得到数组\(b\)。

从理论上来说上面这种枚举+贪心的方法肯定能得到最终的答案，但是时间复杂度达到了\(o(n^2)\)，这是不能接受的。我们再仔细分析一下，会发现符合要求的\(x\)是连续的、在一个区间里面的，原因如下：

我们假设符合要求的\(x\)的区间为\([L, R]\)。现在我们将\(x=R\)情况对应的组合进行操作可以得到\(x=R+1\)的情况：将数组\(a\)中\(n-x\)个最小的数字中最大的一个数字（称它为\(i\)）与数组\(b\)中\(x\)个最小的数字中最小的一个数字（称它为\(j\)）进行组合，这时候一定是因为\(i<j\)从而取\(min\)操作时不能得到\(j\)所以不符合条件。而对于之后的\(x=R+1, ..., x=n\)的情况，\(b\)中\(x\)个数字最小的数字中最小的数字是不变的，而\(a\)中\(x\)个最小的数字是不断变小的，所以之后的情况也都是不符合的。同理我们也可以从\(x=L-1,..., x=0\)这些情况中得到同样的结论。

通过这个结论，我们可以通过两次二分查找，找到符合条件的\(x\)区间\([L, R]\)的\(L\)和\(R\)，这样就可以将时间复杂度优化到\(o(nlogn)\)。

AC代码

#include 
   
    #include 
    
     #include 
     
       const int maxn = 2e5 + 5; int a[maxn], b[maxn]; int check(int mid, int n) { // 0 suit;  1 l = mid + 1; 2 r = mid - 1;	for (int i = 0; i < mid; i++) {		if (b[i] > a[n - mid + i]) {			return 2;		}	}	for (int i = 0; i < n - mid; i++) {		if (a[i] > b[mid + i]) {			return 1;		}	}	return 0;}	int main() {	int T, n;	scanf("%d", &T);	while (T--) {		scanf("%d", &n);		for (int i = 0; i < n; i++) {			scanf("%d", &b[i]);		}		std::sort(b, b + n);		int tot = 0, cur = 0;		for (int i = 0; i < 2 * n; i++) {			if (i + 1 == b[cur]) {				cur++;			} else {				a[tot++] = i + 1;			}		}		int l = 0, r = n;		while (l <= r) {			int mid = (l + r) >> 1;			if (check(mid, n) != 1) {				r = mid - 1;			} else {				l = mid + 1;			}		}		int L = l;		l = 0, r = n;		while (l <= r) {			int mid = (l + r) >> 1;			if (check(mid, n) != 2) {				l = mid + 1;			} else {				r = mid - 1;			}		}		int R = r;		printf("%d\n", R - L + 1);	} 	return 0;}