题意
将 2 n个数，分成n 对。其中 x对进行取小操作，剩下的数进行取大操作。给你一个 n 个元素的序列a 。问你x 可以为多少种数，能得到 a 数组。
思路
将出现过的数字放在 a数组 未出现过的数放在 b数组
设 R为 最多可以取多少次小 二分求 R
设 L 为 最多可以取多少次大 二分求 L 则n−L 为最少可以取多少次小
最终x 范围为R−(n−L)+1
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } typedef long long LL; typedef pair<int, int>PII; const int N = 400100; int n; bool st[N]; vector<int>a, b; void solve() { cin >> n; a.clear(); b.clear(); memset(st, 0, sizeof st); for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); st[x] = true; } for (int i = 1; i <= 2 * n; ++i) { if (st[i])a.push_back(i); else b.push_back(i); } int l = 0, r = n, L, R; while (l < r) { //求出 int mid = l + r + 1 >> 1; bool flag = true; for (int i = 0; i < mid; ++i) { if (a[i] > b[n - mid + i]) { flag = false; } } if (flag)l = mid; else r = mid - 1; } R = l; l = 0, r = n; while (l < r) { int mid = l + r + 1 >> 1; bool flag = true; for (int i = 0; i < mid; ++i) { if (a[n - mid + i] < b[i]) { flag = false; } } if (flag)l = mid; else r = mid - 1; } L = l; cout << R - n + L + 1 << endl; } int main() { int t; cin >> t; while (t--) solve(); return 0; }
