There are n servers where the ith server can serve request[i] number of requests and has an initial health of health[i] units. Each second, the developers send the maximum possible number of requests that can be served by all the available servers. With the request, the developers can also send a virus to one of the servers that can decrease the health of a particular server by k units. The developers can choose the server where the virus should be sent. A server goes down when its health is less than or equal to 0. After all the servers are down, the developers must send one more request to conclude the failure of the application. Find the minimum total number of requests that the developers must use to bring all the servers down.
constraints :
1<=n<=1e5
1<=req[i],health[i]<=5e3
1<=k<=5e3
example =
n=2
k=3
req=[3,4]
health=[4,6]
ans = 21
can you share your approach for this problem. I didn't get idea how to solve it.
Obviously we should focus on taking down one server at a time. Suppose instead of health[i] we have time[i] representing the number of seconds to take down server i. Then, we can use an exchange argument to prove we should take down the servers in descending order of req[i]/time[i]. Consider the following drawing of removing two adjacent servers with time on x-axis and total requests on y-axis, it shows that we should remove server 2 first if req2*time1 is greater than req1*time2, or equivalently if req2/time2 is greater than req1/time1
https://imgur.com/a/wojM3KI
See this blog for more examples of exchange arguments: https://codeforces.me/blog/entry/63533
but it give wrong answer on this test
n=2 k=4
health=[1,2]
req=[2,3]
ans=8
gives=9
Note that
time[i] = health[i] / ksotime=[1,1]in your example and we should take down server 2 firstHow it is going to help, dividing every server's health by k will not affect the order since all of them are divided by k.
It's integer floor division so it won't affect the values linearly