codeforces 1463D - pairs

传送门

题意： 1 到 2n ，2n个数，两两一组组成n组，其中x组取组中较小的，另外的组取组中较大的，给出取出的n个数，可以任意分组，问x取值有几种

将1到2n按要求分到两个容器a，b中

二分，判断mid的时候，是判断a的前mid个是否对应小于b的后mid个，a的后n-mid个是否对应大于b的前n-mid个

刚开始觉得因为求x的区间，不是YYNN之类的，大概会是NNNNNNYYYYYNNNN这样的感觉，就不能二分（…

但其实可以，在判断的时候看一下是在哪里不符合的然后相应的移动L和R就行（当a的前mid个不能对应小于b的后mid个的时候说明mid太大了，当a的后n-mid个不能对应大于b的前n-mid个的时候说明mid太小了，二分一个x的上下界 ，当刚好都能符合的时候根据要找最大值还是最小值移动mid

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
constexpr int N = 4e5 + 10;

vector<int> a, b;
bool vis[N];

int n;

inline void init() {
    a.clear(), b.clear();
    for (int i = 1; i <= 2 * n; ++i) {
        vis[i] = 0;
    }
}

inline int check(int x) {
    for (int i = 0, j = n - x; i < x, j < n; ++i, ++j) {
        if (a[i] > b[j]) return -1;
    }
    for (int i = x, j = 0; i < n, j < n - x; ++i, ++j) {
        if (a[i] < b[j]) return 1;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        init();
        cin >> n;
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            a.push_back(x);
            vis[x] = 1;
        }
        sort(a.begin(), a.end(), [](int x, int y) { return x < y; });
        for (int i = 1; i <= 2 * n; ++i) {
            if (!vis[i]) {
                b.push_back(i);
            }
        }
        sort(b.begin(), b.end(), [](int x, int y) { return x < y; });
        int l = 0, r = n, mid, mxX = 0, mnX = 0;
        while (l <= r) {
            mid = l + r >> 1;
            if (check(mid) == 0) {
                mxX = mid;
                l = mid + 1;
            } else {
                if(check(mid) < 0) {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
        }
        l = 0, r = n;
        while (l <= r) {
            mid = l + r >> 1;
            if (check(mid) == 0) {
                mnX = mid;
                r = mid - 1;
            } else {
                if(check(mid) < 0) {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
        }
        cout << mxX - mnX + 1 << endl;
    }
}

最后

以上就是奋斗小蝴蝶为你收集整理的codeforces 1463D - pairs的全部内容，希望文章能够帮你解决codeforces 1463D - pairs所遇到的程序开发问题。

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