I need to fight N monsters whose energy is given by the array Arr[1:n]. I need to maximize my glory points which are defined as the net number of battles won. Initially, I have Energy E and 0 glory points. I must battle the monsters sequentially from left to right in a queue. I have the following 4 options: 1. If my current energy is greater than the monster's energy I can defeat it and lose energy equal to that of the monster's energy and gain a glory point. 2. I may choose not to compete with the monster. Then neither my energy nor my glory point changes. 3. I may delay my encounter with the monster by sending him to the back of the queue. Then neither my energy nor my glory point changes. 4. I may lose to the monster to gain its energy but lose a glory point. My energy should always be greater than 0. And glory points at all times greater than or equal to 0. Find the maximum value of glory points. Constraints: 1=<N<=1000 1<=E<=10^6 1<=Arr[i]<=10^6
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 154 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | TheScrasse | 145 |
| 10 | nor | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.07.2024 03:21:08 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
A clarification. If energy of monster you're battling with is lesser than your energy, still you can choose to lose from that monster to gain its energy. Am I correct?
Yes you can
If that is true, then notice that due to sending a monster at the back of the queue option, you can fight the monsters in any order (which is easy to prove).
Sort all the monsters on the basis of energies. Fix the number of monsters you lose to. Call it $$$k$$$. It is optimal that you lose to $$$k$$$ monsters with highest energies (suffix of length $$$k$$$ in the sorted list).
It is optimal to win against some prefix of monsters in the list. For every $$$k$$$, find the highest $$$j$$$ such that $$$j \le n-k$$$ and $$$sum[1..j] \le sum[n-k+1..n] + E$$$. Note that $$$sum[i..j]$$$ denotes the sum of energies of monster from $$$[i..j]$$$ in the sorted list. You score for that $$$k$$$ is $$$j-k$$$.
Do this for all possible $$$k$$$ and find maximal score. You may use binary search for that.
Can you give a proof that the monsters can be ordered in any possible way we want
Let's say you have m monsters left at a given point — a_1, a_2, ... a_m, and you want to battle monster a_i. You can send all monsters from a_1 to a_i-1 to the back so that now a_i is the first monster in the queue. You can fight it now.
The same can now be applied to remaining monsters.
I don't think we need to select k monsters to defeat just maintain a multiset keep eliminating the lowest monster until you can, update the answer with current points and then lose by the most powerful monster. this easily works in O(nlogn), and log factor can be further improved by 2 pointers.