problem.txt (3116B)
1 D. Lock and Unlock 2 time limit per test2 seconds 3 memory limit per test256 megabytes 4 You are given an integer array [a1,a2,…,an] 5 . Initially, all the elements are unlocked. 6 7 You may perform the following operation on array a 8 any number of times (possibly zero): 9 10 Choose an integer k 11 (1≤k≤n 12 ) and choose exactly k 13 distinct indices. The elements at these indices are locked for the current operation. This step incurs a cost equal to k 14 . 15 16 Choose one of the following two actions: 17 18 Increase every unlocked element by 1 19 ; 20 Decrease every unlocked element by 1 21 . 22 This step does not incur any additional cost. 23 24 Unlock all the elements. This step does not incur any additional cost. 25 The total cost is equal to the sum of the individual costs over all the operations performed. 26 27 Determine the minimum possible total cost to make all the elements of the array a 28 equal. Furthermore, among all the ways to achieve this minimum possible total cost, find the minimum number of operations required. 29 30 Input 31 The first line of the input contains a single integer t 32 (1≤t≤2⋅104 33 ) — the number of test cases. The description of each test case follows. 34 35 The first line of each test case contains a single integer n 36 (2≤n≤2⋅105 37 ) — the length of the array a 38 . 39 40 The second line of each test case contains n 41 integers a1,a2,…,an 42 (−109≤ai≤109 43 ) — the elements of the array a 44 . 45 46 It is guaranteed that the sum of n 47 over all the test cases does not exceed 2⋅105 48 . 49 50 Output 51 For each test case, print two space-separated integers on a new line — the minimum possible total cost to make all the elements equal, and the minimum number of operations required to make all the elements equal with the minimum possible total cost. 52 53 --- 54 55 [a_1,a_2,...,a_n] where all elements are locked 56 57 can do this any number of times: 58 - choose a number k >= 1 k <= n and choose k distinct indices all of these elements are locked, with a cost of k 59 - choose one of the two actions 60 1. increased every unlocked by 1 61 2. decrease every unlocked by 1 62 - unlock all elements 63 64 - find min cost to make all elements equal 65 - find the minimum number of operations required too, using min cost approach 66 67 - constraints 68 - 2000 test cases 69 - 10_000 arr len max 70 - numbers between -10^9 and 10^9 71 72 - so we must do this in nlogn / linear time 73 74 75 3 76 1 2 3 77 78 1 2 3 79 80 lock 1, decrement 81 82 1 1 2 83 84 lock final element, increment 85 86 2 2 2 87 88 cost: 2 89 ops: 2 90 91 idea: find highest and lowest. find number of high and low elements and then move towards whichever one has less elements. 92 sort first(?) order doesn't matter in terms of positions. 93 94 --- 95 2 96 -1 -1 97 98 cost: 0 99 ops: 0 100 101 --- 102 4 103 18 -2 9 11 104 105 can start on either end. lock low 106 107 108 17 -2 8 10 109 110 16 -2 7 9 111 112 ... 113 114 7 -2 -2 0 115 116 7 -1 -1 1 117 118 7 0 0 2 119 120 7 1 1 3 121 122 7 2 2 4 123 124 7 3 3 5 125 126 7 4 4 6 127 128 7 5 5 7 (cost 2) 129 130 7 6 6 7 (cost 2) 131 132 7 7 7 7 133 134 cost: 22 (2 additional at the end) 135 136 18 -- 2 = 20 137 138 note: number of operations == max - min or smt like that 139 note: we can then compute the stepwise deltas between elements, using this as a multiplier for our selections 140 141 --- 142 9 143 9 9 8 2 4 4 3 5 3 144 --- 145 3 146 6 67 7 147 ---