codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2096B.md (2969B)


      1 Source: https://codeforces.com/problemset/problem/2096/B
      2 
      3 B. Wonderful Gloves
      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 You are the proud owner of many colorful gloves, and you keep them in a drawer. Each glove is in one of $n$ colors numbered $1$ to $n$. Specifically, for each $i$ from $1$ to $n$, you have $l_i$ left gloves and $r_i$ right gloves with color $i$.
     22 
     23 Unfortunately, it's late at night, so you can't see any of your gloves. In other words, you will only know the color and the type (left or right) of a glove after you take it out of the drawer.
     24 
     25 A matching pair of gloves with color $i$ consists of exactly one left glove and one right glove with color $i$. Find the minimum number of gloves you need to take out of the drawer to guarantee that you have at least $k$ matching pairs of gloves with different colors.
     26 
     27 Formally, find the smallest positive integer $x$ such that:
     28 
     29 * For any set of $x$ gloves you take out of the drawer, there will always be at least $k$ matching pairs of gloves with different colors.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$, $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$) — the number of different colors, and the minimum number of required matching pairs of gloves.
     36 
     37 The second line of each test case contains $n$ integers $l_1, l_2, \ldots, l_n$ ($1 \leq l_i \leq 10^9$) — the number of left gloves with color $i$ for each $i$ from $1$ to $n$.
     38 
     39 The third line of each test case contains $n$ integers $r_1, r_2, \ldots, r_n$ ($1 \leq r_i \leq 10^9$) — the number of right gloves with color $i$ for each $i$ from $1$ to $n$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the minimum number of gloves you need to take out of the drawer.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 3 3
     55 
     56 1 1 1
     57 
     58 1 1 1
     59 
     60 1 1
     61 
     62 100
     63 
     64 1
     65 
     66 3 2
     67 
     68 100 1 1
     69 
     70 200 1 1
     71 
     72 5 2
     73 
     74 97 59 50 87 36
     75 
     76 95 77 33 13 74
     77 
     78 10 6
     79 
     80 97 59 50 87 36 95 77 33 13 74
     81 
     82 91 14 84 33 54 89 68 34 14 15
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 6
     89 101
     90 303
     91 481
     92 1010
     93 ```
     94 
     95 Note
     96 
     97 In the first test case, you must take out all of the gloves, so the answer is $6$.
     98 
     99 In the second test case, the answer is $101$. If you take out $100$ gloves or fewer, then it is possible that all of them are left gloves, which means you won't have a matching pair of gloves.
    100 
    101 In the third test case, the answer is $303$. If you only take out $302$ gloves, then one possible scenario is as follows:
    102 
    103 * Color $1$: $100$ left gloves, $200$ right gloves
    104 * Color $2$: $1$ left glove, $0$ right gloves
    105 * Color $3$: $0$ left gloves, $1$ right glove
    106 
    107 You only have multiple matching pairs of gloves with color $1$. So you won't have at least $2$ matching pairs of gloves with different colors.