1690E.md (2932B)
1 Source: https://codeforces.com/problemset/problem/1690/E 2 3 E. Price Maximization 4 5 time limit per test 6 7 2 seconds 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 A batch of $n$ goods ($n$ — an even number) is brought to the store, $i$-th of which has weight $a_i$. Before selling the goods, they must be packed into packages. After packing, the following will be done: 22 23 * There will be $\frac{n}{2}$ packages, each package contains exactly two goods; 24 * The weight of the package that contains goods with indices $i$ and $j$ ($1 \le i, j \le n$) is $a_i + a_j$. 25 26 With this, the cost of a package of weight $x$ is always $\left \lfloor\frac{x}{k}\right\rfloor$ burles (rounded down), where $k$ — a fixed and given value. 27 28 Pack the goods to the packages so that the revenue from their sale is maximized. In other words, make such $\frac{n}{2}$ pairs of given goods that the sum of the values $\left \lfloor\frac{x_i}{k} \right \rfloor$, where $x_i$ is the weight of the package number $i$ ($1 \le i \le \frac{n}{2}$), is maximal. 29 30 For example, let $n = 6, k = 3$, weights of goods $a = [3, 2, 7, 1, 4, 8]$. Let's pack them into the following packages. 31 32 * In the first package we will put the third and sixth goods. Its weight will be $a_3 + a_6 = 7 + 8 = 15$. The cost of the package will be $\left \lfloor\frac{15}{3}\right\rfloor = 5$ burles. 33 * In the second package put the first and fifth goods, the weight is $a_1 + a_5 = 3 + 4 = 7$. The cost of the package is $\left \lfloor\frac{7}{3}\right\rfloor = 2$ burles. 34 * In the third package put the second and fourth goods, the weight is $a_2 + a_4 = 2 + 1 = 3$. The cost of the package is $\left \lfloor\frac{3}{3}\right\rfloor = 1$ burle. 35 36 With this packing, the total cost of all packs would be $5 + 2 + 1 = 8$ burles. 37 38 Input 39 40 The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test. 41 42 The descriptions of the test cases follow. 43 44 The first line of each test case contains two integers $n$ ($2 \le n \le 2\cdot10^5$) and $k$ ($1 \le k \le 1000$). The number $n$ — is even. 45 46 The second line of each test case contains exactly $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). 47 48 It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$. 49 50 Output 51 52 For each test case, print on a separate line a single number — the maximum possible total cost of all the packages. 53 54 Example 55 56 Input 57 58 ``` 59 6 60 61 6 3 62 63 3 2 7 1 4 8 64 65 4 3 66 67 2 1 5 6 68 69 4 12 70 71 0 0 0 0 72 73 2 1 74 75 1 1 76 77 6 10 78 79 2 0 0 5 9 4 80 81 6 5 82 83 5 3 8 6 3 2 84 ``` 85 86 Output 87 88 ``` 89 8 90 4 91 0 92 2 93 1 94 5 95 ``` 96 97 Note 98 99 The first test case is analyzed in the statement. 100 101 In the second test case, you can get a total value equal to $4$ if you put the first and second goods in the first package and the third and fourth goods in the second package. 102 103 In the third test case, the cost of each item is $0$, so the total cost will also be $0$.