Tikinti (Həll təhlili)

Körpünün uzunluğunu $d$ ikili axtarışla tapaq. Əvvəlcə d \in [Left; Right] = [0; INF] kimi qəbul edək.

Sonra bu alt məsələyə baxaq: tələb olunan körpü uzunluğunu tam olaraq Mid = (Left + Right) / 2 etmək olarmı? Bunun üçün mövcud olanlardan neçə taxta uzunluğu $Mid$ əldə edə biləcəyimizi hesablayacağıq.

Uzunluğu l_i olan taxtadan \lfloor l_i / Mid \rfloor uzunluğu olan $Mid$ taxtalar əldə etmək olar. Bu dəyəri bütün taxtalar üzrə cəmləşdirərək, kəsiklərdən hansı uzunluqda $Mid$ taxtalar əldə edə biləcəyimizi öyrənəcəyik:

Əgər belə taxtaların ümumi sayı $m$-dən az deyilsə, bu o deməkdir ki, uzunluğu artırmağa cəhd edə bilərik — Left = Mid + 1 təyin edirik. Əks halda yuxarı həddi azaldırıq: Right = Mid.

Problemə cavab Left - 1 dəyəri olacaqdır.

Misal

Göstərilən nümunədə $4$ taxta var. $6$ taxtadan ibarət körpü tikilməlidir. Əgər taxta uzunluğunu $8$ seçsək, onda mövcud taxtalardan

uzunluğu olan $8$ taxtalar əldə edə bilərik.

Əgər uzunluğu $9$ seçsək, o zaman alınacaq

ki bu da zəruri miqdardan azdır.

Alqoritmin tətbiqi

İstifadə olunan sabitləri müəyyən edək. Mövcud taxtaların uzunluqlarını l_i massivində saxlayırıq.

#define INF 2000000010
#define MAX 1000009
long long a[MAX];

cnt funksiyası mövcudlarından tələb olunan uzunluğu olan $Mid$ taxtalar əldə edə biləcəyimiz miqdarı qaytarır. Bu dəyər aşağıdakı cəm ilə bərabərdir:

long long cnt(long long  Mid) 
{
  if (Mid == 0) return INF;
  long long res = 0;
  for(i = 0; i < n; i++)
    res += a[i] / Mid;
  return res;
}

Proqramın əsas hissəsi. Daxil olunan məlumatları oxuyuruq.

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

d \in [Left; Right] = [0; INF] qiyməti üçün hədlər təyin edirik və ikili axtarışı işə salırıq.

Left = 0;
Right = INF;
while (Left < Right)
{
  Mid = (Left + Right) / 2;

cnt(Mid) dəyəri hər biri $Mid$ uzunluğunda olan taxtaların mövcud olandan əldə edilən sayına bərabərdir. Əgər bu miqdar lazım olan $m$ sayından azdırsa, təxmin edilən taxta uzunluğunu azaltmaq lazımdır: Right = Mid təyin edirik. Əksinə, sol sərhədi artırırıq: Left = Mid + 1.

  if (cnt(Mid) < m) Right = Mid;
  else Left = Mid + 1;
}

Cavabı çıxışa veririk.

printf("%lld\n",Left - 1);