problem.txt (3271B)
1 C. All-in-one Gun 2 time limit per test2 seconds 3 memory limit per test256 megabytes 4 You are developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game. 5 6 You have an all-in-one gun that shoots bullets in a fixed order. There are n 7 bullets in the magazine, the i 8 -th of which deals ai 9 damage. The enemy starts with h 10 health and dies when its health becomes ≤0 11 . 12 13 The gun shoots one bullet per second. After firing all n 14 bullets, it must reload, which takes k 15 seconds. Reloading always restores the same sequence of bullets [a1,a2,…,an] 16 . You cannot reload early; you must empty the magazine first. At the start, the magazine is already full. 17 18 Before the fight begins, you may perform at most one swap: pick any indices 1≤i<j≤n 19 and exchange ai 20 with aj 21 . 22 23 Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap. 24 25 Input 26 Each test contains multiple test cases. The first line contains the number of test cases t 27 (1≤t≤104 28 ). The description of the test cases follows. 29 30 The first line of each testcase contains three integer n 31 , h 32 and k 33 (2≤n≤2⋅105 34 , 1≤h,k≤109 35 ) — the size of magazine, health of your enemy and time required to reload the magazine. 36 37 The second line of each testcase contains n 38 integers a1,a2,…,an 39 (1≤ai≤109 40 ). 41 42 It is guaranteed that the sum of n 43 does not exceed 2⋅105 44 over all test cases. 45 46 47 --- 48 49 - bullet damage array a 50 - a_i is damage done by bullet i 51 - enemy has h health to start 52 - one bullet per second 53 - k seconds to reload 54 - can't reload early 55 - you may swap two bullets at the start a_i -> a_j a_j -> a_i 56 57 --- 58 59 60 5 10 1 61 4 2 3 5 3 62 63 n,h,k 64 65 5 elements 66 h = 10 == health start 67 k = 1 == seconds to reload 68 69 4 2 3 5 3 70 71 swap: 2,5 72 73 4 5 3 2 3 74 75 shoot 1,2,3 that's it. 76 77 3 seconds 78 79 heuristic: find section from start that sums to 10. check each swap with smallest value in section and later values to see if this changes things 80 81 --- 82 83 5 10 1 84 4 2 3 7 3 85 86 5 elements 87 10 health 88 1 second reload 89 90 4 2 3 7 3 91 92 4+2+3+7 = 16 93 94 smallest = 2 95 96 2,3 swap does nothing 97 2,7 swap decreases by 1 98 ... 99 100 4 7 3 2 3 101 102 same heuristic as above, but the issue here is that we don't only care about the min value; if we could swap the first with a larger value even 103 if first > second and that'd finish the problem we should do that. 104 105 --- 106 107 3 10 2 108 1 2 3 109 110 two second reload 111 10 health 112 113 3 2 1 114 115 3, 2, 1, (reload), 3, 2 -> 7 116 117 --- 118 119 2 5 3 120 2 1 121 122 2 elements, 3 second reload, 5 health 123 124 since descending order do nothing. 125 126 2,1,reload,2 -> 6 127 128 --- 129 130 3 18 5 131 1 2 3 132 133 3,2,1 134 135 136 --- 137 138 4 10 10 139 1 1 2 2 140 141 2,1,2,1 142 143 --- 144 145 idea: 146 147 - compute sum of array 148 - compute rem = health % sum 149 - rem is then the amount of damage to be dealt in the last magazine 150 - how to compute shortest array ordering that results in sum >= rem 151 - compute default substring s.t. sum >= rem 152 - from 0 -> len: 153 - check if current where we swap smallest on left with largest on right (inclusive of current) would be > target 154 - if so, return this idx + (magTime * magsUsed) 155 - if not continue 156 - how to make this fast: 157 - compute max postfix (exclusive of current) and min prefix (inclusive)