Blimps

Правка en2, от spookymath, 2022-08-05 11:45:42

Hello CodeForces !

I was solving this Problem on CodeChef the other Day. I misinterpreted the question and was thinking of a different variety of the same question.
Problem Link

Originally, the Question says —
You have $$$N$$$ cities where $$$A[i]$$$, $$$0≤A[i]≤10^9$$$ denotes the Unhappiness Value of the $$$i^{th}$$$ city.
You are given two integers $$$X$$$ and $$$Y$$$. For each Blimp sent, you can make one of the following choices —

Operation 1. Make the Blimp Fly over every city, in which case the sadness of every city will decrease by $$$Y$$$.
Operation 2. Choose a city $$$i$$$, where ($$$1≤i≤N$$$), and shower confetti over city $$$i$$$. In this case, the sadness of cities $$$1, 2,..., i−1$$$ will decrease by $$$Y$$$, the sadness of city $$$i$$$ will decrease by $$$X$$$, and cities $$$i+1, i+2,..., N$$$ see no change in sadness.

(Note that each of the operation consumes 1 Blimp at a time).

We have to find the minimum number of blimps needed such that, by making the above choice optimally for each blimp, you can ensure that no city is sad (i.e, in the end every city has sadness $$$A[i]≤0$$$).

Modification
Operation 1 — Instead of Making the Blimp Fly over every city, I will only reduce the unhappiness of the $$$i^{th}$$$ City by $$$Y$$$.
Operation 2 (Confetti) — Stays the same.

What would be the Minimum Number of Blimps Needed ?

My Approach -

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский spookymath 2022-08-05 12:24:48 0 (published)
en4 Английский spookymath 2022-08-05 12:23:40 103 Final Edit
en3 Английский spookymath 2022-08-05 12:11:47 2094
en2 Английский spookymath 2022-08-05 11:45:42 1732 Tiny change: ' question.\n[Problem' -> ' question. <br>\n[Problem'
en1 Английский spookymath 2022-08-05 10:19:04 220 Initial revision (saved to drafts)