Olimpiada#7503

Olimpiada (Həll təhlili)

Yarışmaya ümumilikdə $s = \sum_{i = 1}^{n} a_{i}$ s = \sum_{i=1}^n a_i iştirakçı gəlib. Hər auditoriya $m$ kompüter ilə təmin edildiyi üçün, ən azı $⌈ s / m ⌉$ otaq tələb olunacaq.

Tutaq ki, $p$ — bir komandadakı iştirakçıların ən böyük sayıdır (bütün $a_{i}$ a_i ədədlərinin maksimum dəyəri). Əgər $p > ⌈ s / m ⌉$ p > ⌈s/m⌉ olsa, o zaman ən azı $p$ otaq tələb olunacaq.

Konstruktiv olaraq göstərmək olar ki, həmişə olimpiadanın keçirilməsi üçün $ma x (⌈ s / m ⌉, p)$ max(⌈s/m⌉, p) auditoriya kifayətdir.

Misal

Olimpiadaya $2 + 3 + 4 + 1 + 2 = 12$ 2 + 3 + 4 + 1 + 2 = 12 şagird gəlib. Hər sinif $3$ kompüter ilə təmin olunduğuna görə, olimpiadanın keçirilməsi üçün ən azı $12/3 = 4$ 12 / 3 = 4 sinif tələb olunur.

Ən böyük iştirakçı sayı üçüncü komandadır — $4$ nəfər. Onları fərqli $4$ sinifdə bir-bir oturtmaq olar.

Məsələn, iştirakçıların aşağıdakı şəkildə oturması mümkündür:

Alqoritmin təcrübəsi

Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&n,&m);

Ümumi iştirakçı sayını $s$ və ən böyük komandanın ölçüsünü $p$ hesablayırıq.

p = 0;
for (i = 0; i < n; i++)
{
  scanf("%d",&x);
  s += x;
  if (x > p) p = x;
}

C++

$s / m$ tavanı olan dəyər $r es = ⌈ s / m ⌉$ res = ⌈s/m⌉ kimi $(s + m - 1) / m$ (s + m - 1) / m hesablanır.

res = (s + m - 1) / m;

Əgər $p > ⌈ s / m ⌉$ p > ⌈s/m⌉ olsa, cavab $p$ olacaq.

if (res < p) res = p;

Cavabı çıxışa yazırıq.

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