Codeforces1463 D. Pairs（有多返回值二分）

You have 2???? integers 1,2,…,2????. You have to redistribute these 2???? elements into ???? pairs. After that, you choose ???? pairs and take minimum elements from them, and from the other ????−???? pairs, you take maximum elements.

Your goal is to obtain the set of numbers {????1,????2,…,????????} as the result of taking elements from the pairs.

What is the number of different ????-s (0≤????≤????) such that it’s possible to obtain the set ???? if for each ???? you can choose how to distribute numbers into pairs and from which ???? pairs choose minimum elements?

Input
The first line contains a single integer ???? (1≤????≤1000) — the number of test cases.

The first line of each test case contains the integer ???? (1≤????≤2⋅105).

The second line of each test case contains ???? integers ????1,????2,…,???????? (1≤????1<????2<⋯<????????≤2????) — the set you’d like to get.

It’s guaranteed that the sum of ???? over test cases doesn’t exceed 2⋅105.

Output
For each test case, print one number — the number of different ????-s such that it’s possible to obtain the set ????.

Example
inputCopy
3
1
1
5
1 4 5 9 10
2
3 4
outputCopy
1
3
1
Note
In the first test case, ????=1 is the only option: you have one pair (1,2) and choose the minimum from this pair.

In the second test case, there are three possible ????-s. If ????=1, then you can form the following pairs: (1,6), (2,4), (3,5), (7,9), (8,10). You can take minimum from (1,6) (equal to 1) and the maximum elements from all other pairs to get set ????.

If ????=2, you can form pairs (1,2), (3,4), (5,6), (7,9), (8,10) and take the minimum elements from (1,2), (5,6) and the maximum elements from the other pairs.

If ????=3, you can form pairs (1,3), (4,6), (5,7), (2,9), (8,10) and take the minimum elements from (1,3), (4,6), (5,7).

In the third test case, ????=0 is the only option: you can form pairs (1,3), (2,4) and take the maximum elements from both of them.

题意：
$1,2,3,4,...,2\ast n$，这些数划分为n对数。然后你对其中一些对取$min$，一些对取$max$，然后得到$b$数组。设取$min$的个数为$x$。
现在给你$b$数组，存在多少个$x$使得最终结果为$b$数组。

思路：

• 先将b数组排序，假设$2n$个数中除去b数组剩下的数组成$a$数组。
• 二分这个$x$，找到其上下界，差值加一就是结果。
• 假设当前二分值为$mid$，则我们要让b数组中前$mid$个数为取$min$操作得到的，后$n-mid$个数为取$max$操作得到的。则我们让$b$数组前$mid$个数和$a$数组后$mid$个数组成数对，$b$数组后$n-mid$个数与$a$数组前$n-mid$个数配对。
• 如果$mid$个数的取$min$操作无法完成，说明$x$要变小；如果$n-mid$个数的取$max$操作无法完成，说明$x$要变大；否则说明该$mid$值合理。

#include <algorithm>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
typedef long long ll;
const int maxn = 4e5 + 7;
int vis[maxn];
vector<int>v1,v2;
int n;
int check(int mid) { //让v1前mid个和v2后mid个配对
    for(int i = 0;i < mid;i++) {
        if(v1[i] > v2[n - mid + i]) {
            return 1; //需要更小的x
        }
    }
    for(int i = 0;i < n - mid;i++) {
        if(v1[i + mid] < v2[i]) return 2; //需要更大x
    }
    return 0; //mid成立
}

int main() {
    int T;scanf("%d",&T);
    while(T--) {
        v1.clear();
        v2.clear();
        scanf("%d",&n);
        for(int i = 1;i <= 2 * n;i++) vis[i] = 0;
        for(int i = 1;i <= n;i++) {
            int x;scanf("%d",&x);
            vis[x] = 1;
        }
        for(int i = 1;i <= 2 * n;i++) {
            if(vis[i]) {
                v1.push_back(i);
            } else {
                v2.push_back(i);
            }
        }
        int l = 0,r = n;
        int L = n;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid) != 2) {
                L = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        l = 0,r = n;
        int R = n;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid) != 1) {
                R = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
//        printf("%d %dn",L,R);
        printf("%dn",R - L + 1);
    }
    return 0;
}

最后

以上就是能干泥猴桃为你收集整理的Codeforces1463 D. Pairs（有多返回值二分）的全部内容，希望文章能够帮你解决Codeforces1463 D. Pairs（有多返回值二分）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。