1704C.md (2612B)
1 Source: https://codeforces.com/problemset/problem/1704/C 2 3 C. Virus 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There are $n$ houses numbered from $1$ to $n$ on a circle. For each $1 \leq i \leq n - 1$, house $i$ and house $i + 1$ are neighbours; additionally, house $n$ and house $1$ are also neighbours. 22 23 Initially, $m$ of these $n$ houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently. 24 25 Every day, the following things happen in order: 26 27 * Cirno chooses an uninfected house, and protect it permanently. 28 * All uninfected, unprotected houses which have at least one infected neighbor become infected. 29 30 Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect. 31 32 Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever. 33 34 Input 35 36 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of test cases follows. 37 38 The first line of each test case consists of two positive integers $n, m$ ($5 \leq n \leq 10^9$, $1 \leq m \leq \min(n, 10^5)$) — the number of houses on the circle, and the number of houses that are initially infected. 39 40 The second line of each test case consists of $m$ distinct positive integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$) — the indices of the houses infected initially. 41 42 It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$. 43 44 Output 45 46 For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end. 47 48 Example 49 50 Input 51 52 ``` 53 8 54 55 10 3 56 57 3 6 8 58 59 6 2 60 61 2 5 62 63 20 3 64 65 3 7 12 66 67 41 5 68 69 1 11 21 31 41 70 71 10 5 72 73 2 4 6 8 10 74 75 5 5 76 77 3 2 5 4 1 78 79 1000000000 1 80 81 1 82 83 1000000000 4 84 85 1 1000000000 10 16 86 ``` 87 88 Output 89 90 ``` 91 7 92 5 93 11 94 28 95 9 96 5 97 2 98 15 99 ``` 100 101 Note 102 103 In the first test case: 104 105 At the start of the first day, house $3$, $6$, $8$ are infected. Choose house $2$ to protect. 106 107 At the start of the second day, house $3$, $4$, $5$, $6$, $7$, $8$, $9$ are infected. Choose house $10$ to protect. 108 109 At the start of the third day, no more houses are infected. 110 111 In the second test case: 112 113 At the start of the first day, house $2$, $5$ are infected. Choose house $1$ to protect. 114 115 At the start of the second day, house $2$, $3$, $4$, $5$, $6$ are infected. No more available houses can be protected.