k altmassivə bölünmə#9020

k altmassivə bölünmə (Həll təhlili)

Optimal qiyməti ikili axtarış vasitəsilə tapacağıq. Aydındır ki, o, $1$ -dən kiçik ola bilməz (çünki massivdəki rəqəmlər təbii ədədlərdir) və bütün elementlərin cəmini keçə bilməz. Sərhədləri quraq: $so l = 1, s a g ˘$ sol = 1, sağ = bütün massiv ədədlərinin cəmi. Onda cavab mütləq $[so l; s a g ˘]$ [sol; sağ] aralığında yerləşir.

Yardımçı alt məsələyə baxaq: massivə elə $k$ altmassivə bölmək olarmı ki, bütün $k$ altmassivin içindəki maksimal cəm verilmiş $s_{0}$ s_0 dəyərindən artıq olmasın? Əgər massivdə $s_{0}$ s_0-dan böyük ən azı bir element varsa, belə bölmə mümkün deyil. Digər hallarda, element cəmi $s_{0}$ s_0-dan artıq olmayan altmassivləri ardıcıl formalaşdıracağıq. Nəticədə $k$ -dan çox olmaması şərtilə $k$ altmassiv alınarsa, belə bölmə mümkündür.

Misal

İkinci misalda, müxtəlif $s_{0}$ s_0 dəyərlərində massivə altmassivlərə bölməyi nəzərdən keçirək:

Alqoritmin reallaşdırılması

$M A X = 1 0^{6}$ MAX = 10^6 sabitinin və işçi massiv $m$ -in elan edilməsi.

#define MAX 1000000
int m[MAX];

f funksiyası elə $1$ qaytarır ki, massivə elə $k$ altmassivə bölmək olar ki, bütün $k$ altmassivlərin içində maksimal cəm verilmiş $s_{0}$ s_0 dəyərindən artıq olmasın.

int f(long long s0)
{
  long long sum = 0;
  int cnt = 1;
  for (int i = 0; i < n; i++)
  {

Əgər massivdə hansısa element $s_{0}$ s_0-dan böyükdürsə, belə bölmə mümkün deyil.

    if (m[i] > s0) return 0;

Cari altmassivin cəmini hesablamaq.

    sum += m[i];

Cari cəm $s_{0}$ s_0-ı üstələdikdə, altmassivlərin sayğacını $c n t$ $1$ artırırıq və növbəti altmassivin cəmini toplamağa başlayırıq.

    if (sum > s0)
    {
      sum = m[i];
      cnt++;
    }
  }

Əgər massiv $k$ -dan çox olmayan altmassivə bölünə bilərsə, deməli, onu tam $k (k \leq n)$ k~(k \le n) altmassivə bölmək olar.

  if (cnt <= k) return 1;
  return 0;
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq. $s a g ˘$ sağ dəyişənində bütün massiv elementlərinin cəmini hesablayırıq.

scanf("%d %d", &n, &k);
left = 1; right = 0;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  right += m[i];
}

C++

Axtarılan minimal maksimum altmassiv cəm $[so l; s a g ˘]$ [sol; sağ] aralığında yerləşir. İkili axtarışı bu intervalda başlatırıq.

while (left < right)
{
  mid = (left + right) / 2;
  if (f(mid) == 1)
    right = mid;
  else
    left = mid + 1;
}

C++

Cavabı çap edirik.

printf("%lld\n", left);