Drying#5363

Drying (Editorial)

Let $ma x$ be the largest value among all $a_{i}$ a_i. Obviously, after $ma x$ minutes, all the laundry will dry naturally, even without using the radiator.

Let the answer be a value $m$ . This means that all items containing at most $m$ units of water will have enough time to dry naturally. Any item that contains more than $m$ units of water will require additional drying on the radiator.

We assume that each item loses $1$ unit of water per minute, regardless of whether it is on the radiator or not. However, if an item is placed on the radiator, it loses an additional $k - 1$ k - 1 units of water per minute, meaning it loses $k$ units per minute in total.

If $m$ minutes are enough to dry all the items, then each item with $a_{i} > m$ a_i > m must be additionally dried using the radiator. The amount of water that won't evaporate naturally is $a_{i} - m$ a_i - m. Since the radiator removes $k - 1$ k - 1 extra units of water per minute, this item will require

⌈ \frac{a _{i} - m}{k - 1} ⌉

\left\lceil {a_i - m \over k - 1} \right\rceil

minutes of radiator time.

The total number of minutes $i = 1 \sum n ⌈(a_{i} - m) / (k - 1)⌉$ \displaystyle \sum_{i=1}^n \lceil (a_i - m) / (k - 1) \rceil the radiator is used must not exceed $m$ , since only one item can be dried per minute. The summation is taken over all indices i for which $a_{i} > m$ a_i > m.

Thus, the check is performed as follows: if, for a given value of $m$ , the total required radiator time does not exceed $m$ , then this value of $m$ is considered valid. The smallest valid value of $m$ can be found using binary search.

Example

Initially, there are three items with water amounts: $(2, 3, 9)$ (2, 3, 9).

In the first minute, place the third item on the radiator. The state becomes: $(1, 2, 4)$ (1, 2, 4).

In the second minute, again place the third item on the radiator. The state becomes: $(0, 1, 0)$ (0, 1, 0).

In the third minute, the second item dries naturally. The final state is: $(0, 0, 0)$ (0, 0, 0).

Let's consider the value $m = 2$ m = 2. In this case, all items containing no more than $2$ units of water will dry naturally.

The remaining items will require drying using the radiator.

The second item contains $3$ units of water, so the radiator needs to remove $3 - 2 = 1$ 3 - 2 = 1 unit.

The third item contains $9$ units of water, so the radiator needs to remove $9 - 2 = 7$ 9 - 2 = 7 units.

This will take $⌈ 1/4 ⌉ + ⌈ 7/4 ⌉ = 3$ \lceil 1/4 \rceil + \lceil 7/4 \rceil = 3 minutes. This exceeds $m = 2$ m = 2, so two minutes are not enough.

Algorithm implementation

Declare the array.

#define MAX 100001
int a[MAX];

Read the input data.

scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&a[i]);
scanf("%d",&k);

In $r$ minutes, all the laundry will definitely dry, even without using the radiator.

l = 0; r = *max_element(a,a+n);

If $k \leq 1$ k \le 1, then drying with the radiator is equivalent to natural drying, and the radiator provides no advantage.

if (k <= 1) 
{
  printf("%d\n",r); return 0;
}

The minimum required number of minutes $m$ can be found using binary search on the interval $[l; r]$ [l; r].

while (r - l > 1)
{
  m = (r + l) / 2;

The variable $d r y$ accumulates the total number of minutes during which the radiator needs to be used. All the laundry must be dried within $m$ minutes.

  dry = 0;
  for (i = 0; i < n; i++)  
  {
    if (a[i] > m) 
      dry += (a[i] - m + k - 2) / (k - 1);
    if (dry > m) break;
  }
  if (dry > m) l = m; else r = m;
}

C++

Print the answer.

printf("%d\n",r);