Qurutma#5363

Qurutma (Həll təhlili)

Güman edək ki, $ma x$ — bütün $a_{i}$ a_i-lər arasında ən böyük qiymətdir. Aydındır ki, $ma x$ dəqiqə ərzində bütün paltarlar heç bir radiator istifadə etmədən öz-özünə quruyacaq.

Cavabın $m$ olduğunu fərz edək. Bu o deməkdir ki, $m$ -dən az su olan bütün paltarlar öz-özünə quruyacaq. Amma $m$ -dən çox su olan paltarları radiatorun köməyi ilə qurudmaq lazımdır.

Fərz edək ki, hər bir paltar, radiator üzərində olub-olmamasından asılı olmayaraq, hər dəqiqədə bir vahid su itirir. Əgər paltarı radiatora qoyarıqsa, o əlavə olaraq $k - 1$ k - 1 vahid su itirir, yəni ümumilikdə $k$ vahid su itirir.

Əgər paltarların hamısını qurumaq üçün $m$ dəqiqə kifayət edirsə, onda hər bir $a_{i} > m$ a_i > m paltarı əlavə olaraq radiatorun köməyi ilə qurumağa ehtiyac var. Bu, $a_{i} - m$ a_i - m vahid suyun təbii yolla buxarlanmağa çatmayacağı mənasına gəlir. Bir dəqiqə ərzində radiator əlavə olaraq $(k - 1)$ (k - 1) vahid su çıxarır, buna görə də belə bir paltar üçün

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

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

radiator müddəti lazım olacaq.

Radiorun ümumi istifadə müddəti $i = 1 \sum n ⌈(a_{i} - m) / (k - 1)⌉$ \displaystyle \sum_{i=1}^n \lceil (a_i - m) / (k - 1) \rceil m qədər çox olmamalıdır, çünki hər dəqiqədə yalnız bir paltarı qurutmaq mümkündür. Cəmi $a_{i} > m$ a_i > m olan indekslər üzrə götürülür.

Beləliklə, yoxlama belə edilməlidir: əgər verilmiş $m$ üçün ümumi lazım olan radiator dəqiqələri $m$ -dən azdırsa, bu vaxt dəyəri uyğundur. Ən kiçik uyğun $m$ dəyərini binary search ilə axtarırıq.

Misal

Başlanğıcda suda olan üç paltar var $(2, 3, 9)$ (2, 3, 9).

Birinci dəqiqədə üçüncü paltarı radiatora qoyuruq. Beləliklə, bu vəziyyəti əldə edirik: $(1, 2, 4)$ (1, 2, 4).

İkinci dəqiqədə yenidən üçüncü paltarı radiatora qoyuruq. Vəziyyət $(0, 1, 0)$ (0, 1, 0) olur.

Üçüncü dəqiqədə ikinci paltar özü quruyur. Son vəziyyət: $(0, 0, 0)$ (0, 0, 0).

$m = 2$ m = 2 dəyərini nəzərdən keçirək. Bu zaman $2$ vahiddən az su olan bütün paltarlar öz-özünə quruyacaq.

Qalanlar üçün radiatorun köməyi ilə qurumaq lazımdır. İkinci paltarda $3$ vahid su var, buna görə radiatorun köməyi ilə $3 - 2 = 1$ 3 - 2 = 1 vahid suyu çıxarmaq lazımdır.

Üçüncü paltarda $9$ vahid su olduğundan, radiator ilə $9 - 2 = 7$ 9 - 2 = 7 vahid suyu çıxarmaq lazımdır.

Bunun üçün $⌈ 1/4 ⌉ + ⌈ 7/4 ⌉ = 3$ \lceil 1/4 \rceil + \lceil 7/4 \rceil = 3 dəqiqə lazım olacaq. Bu, $m = 2$ m = 2-dən çoxdur. Deməli, iki dəqiqə kifayət etmir.

Alqoritmin həyata keçirilməsi

İş massivi elan edək.

#define MAX 100001
int a[MAX];

Giriş məlumatlarını oxuyuruq.

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

$r$ dəqiqə ərzində bütün paltarlar, radiator istifadə edilmədən belə, quruyacaq.

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

Əgər $k \leq 1$ k \le 1-dirsə, radiator ilə quruma təbii quruma ilə eynidir və radiatorun heç bir üstünlüyü yoxdur.

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

Axtarılan minimal dəqiqə miqdarı m $[l; r]$ [l; r] intervallı üzərində binary search ilə tapıla bilər.

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

$d r y$ dəyişəni radiatorun istifadəsi üçün lazım olan ümumi dəqiqələrin sayını toplayır. Bu zaman $m$ dəqiqə ərzində bütün paltarları qurumaq lazımdır.

  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++

Cavabı çap edirik.

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