DDOSvoid's Blog

CF 1463D Pairs

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1463/problem/D

Solution

令 $nb$ 为不在 $b$ 的数，不妨设 $b$ 和 $n$ 都已经排好序了

我们考虑如果 $x$ 个数取 $min$，$n-x$ 个数取 $max$

那么一定是 $b$ 中前 $x$ 个数取 $min$，后 $n-x$ 个数取 $max$

这个证明直接对于不合法的两组数交换即可

那么我们可以 $O(n)$ 检验 $x$ 是否合法

具体做法就是将 $b[i]$ 与 $nb[n-x+i]$ 配对，其中 $i\in [1,x]$

$b[i]$ 与 $nb[i-x+1]$ 配对，其中 $i\in [x+1,n]$

接下来我们只考虑对于 $1$ 到 $x$ 是否可以配对

我们发现如果 $x$ 合法，那么 $x-1$ 一定合法，也就是说这个东西可以直接二分得到最大的 $x$

这时候我们对于 $x+1$ 到 $n$ 可以采取类似的做法，找到最小的 $x$

这样的话，两个 $x$ 之间就是合法的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#define maxn 200010
using namespace std;

int n, a[maxn], b[maxn];

bool use[maxn * 2]; 

bool checkmin(int x) {
    for (int i = 1; i <= x; ++i) 
        if (b[n - x + i] < a[i]) return 0;
    return 1; 
}

bool checkmax(int x) {
    for (int i = 1; i <= x; ++i)
        if (b[i] > a[n - x + i]) return 0;
    return 1; 
} 

void work() {
    cin >> n; fill(use + 1, use + 2 * n + 1, 0); 
    for (int i = 1; i <= n; ++i) cin >> a[i], use[a[i]] = 1;
    for (int i = 1, j = 0; i <= 2 * n; ++i) if (!use[i]) b[++j] = i;
    int l = 0, r = n, mid, rans, lans;
    while (l <= r) {
        mid = l + r >> 1;
        if (checkmax(mid)) rans = mid, l = mid + 1;
        else r = mid - 1;
    }
    l = 0; r = n;
    while (l <= r) {
        mid = l + r >> 1;
        if (checkmin(mid)) lans = mid, l = mid + 1; 
        else r = mid - 1; 
    } lans = n - lans; 
    cout << rans - lans + 1 << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}