D.pairs

链接：https://codeforces.com/problemset/problem/1463/D
题意：给定1～2*n，再给定操作后需要得到的n个数的序列，让你选择n个pair，每两个数组成一对，假设有x个pairs取min，n-x个取max，最后问有几个x能满足这种序列。
思路：
假设x是固定了，取x个min，n-x个max，那么我们将a数组，也就是题目给的n个数，和b数组另外n个数，进行选择，其实贪心想想可以想到前x个数与b的后x个数取min，后n-x与b的前n-x取max，这样是最优的，假设如果把这两个集合中的数互调，可能会不成立，达不到题目给的序列，假设原始为min<a,b>,max<c,d> 其中假设a<b,c>a,c<d,对调那么min<a,d>,max<b,c> ,由于b不一定小于c所有这样是不优的，那么思路就来了，二分x，选择两个返回值，得到上下界就行了
代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>v1,v2;
bool st[400010];
int n;
int check(int mid)
{
    for(int i=0;i<mid;i++)
        if(v1[i]>v2[n-mid+i])    return 2;
    for(int i=mid;i<n;i++)
        if(v1[i]<v2[i-mid])     return 1;
        return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        v1.clear(),v2.clear();
        cin>>n;
        for(int i=1;i<=2*n;i++)
            st[i]=false;
        int x;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            st[x]=true;
            v1.push_back(x);
        }
        for(int i=1;i<=2*n;i++)
        {
            if(!st[i])
                v2.push_back(i);
        }
        int l=0,r=n;
        int L;
        while(l<r)
        {
            //cout<<l;
            int mid=l+r>>1;
            if(check(mid)!=1)
            {
                r=mid;

            }
            else
                l=mid+1;

        }
        L=r;
        l=0,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(check(mid)!=2)
                l=mid;
            else
                r=mid-1;
        }
        int R=l;
        cout << R - L  + 1 << endl;
    }
    return 0;
}