CF1463D-Pairs

题目:

题目描述:

You have $ 2n $ integers $ 1, 2, \dots, 2n $ . You have to redistribute these $ 2n $ elements into $ n $ pairs. After that, you choose $ x $ pairs and take minimum elements from them, and from the other $ n - x $ pairs, you take maximum elements.

Your goal is to obtain the set of numbers $ {b_1, b_2, \dots, b_n} $ as the result of taking elements from the pairs.

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

输入格式:

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.

The first line of each test case contains the integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ).

The second line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_1 < b_2 < \dots < b_n \le 2n $ ) — the set you’d like to get.

It’s guaranteed that the sum of $ n $ over test cases doesn’t exceed $ 2 \cdot 10^5 $ .

输出格式:

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

样例:

样例输入1:

1
2
3
4
5
6
7

3
1
1
5
1 4 5 9 10
2
3 4

样例输出1:

1
2
3

1
3
1

思路:

实现:

 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

// Problem: CF1463D Pairs
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1463D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int n;
int vis[1000001];
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        yin >> n;
        for (int i = 1; i <= 2 * n; i++)
            vis[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            yin >> x;
            vis[x] = 1;
        }
        int siz = 0, as = 0, is = 0;
        for (int i = 1; i <= n * 2; i++)
        {
            if (vis[i])
                ++siz;
            else
                --siz;
            as = max(as, siz);
            is = min(is, siz);
        }
        yout << n - (as - is) + 1 << endl;
    }
    return 0;
}