Xorvatiya sahilindəki otellər (Həll təhlili)

Otel qiymətlərini $a$ massivində saxlayırıq. $[i...j]$ aralığını yaxşı adlandıracağıq, əgər bu aralıqdakı otel qiymətlərinin cəmi $m$-dən çox olmazsa.

Sürüşən pəncərə metodunu iki indeks $i$ və $j$ ilə həyata keçirək və bu pəncərəni dəstəkləyək ki, mövcud nəzərdən keçirilən interval $[i...j]$ yaxşı olsun. $s$ - $[i...j]$ aralığındakı otel qiymətlərinin cəmi olsun. Əgər s + a[j + 1] \le m, onda mövcud aralığı a[i ... j + 1]-ə qədər genişləndiririk. Əks halda onu a[i + 1 ... j] aralığına qədər qısaldırıq. Bütün nəzərdən keçirilən yaxşı aralıqlar arasında maksimum qiyməti tapırıq.

Nümunə

Verilən nümunə üçün göstəricilərin hərəkətini nəzərdən keçirək.

1. i = 0, j qarşıya hərəkət edir, aralıqdakı $[i...j]$ ədədlərinin cəmi m = 12-dən çox olmayana qədər. $[\mathrm{0...3}]$ aralığında dayanırıq, çünki bu aralıqdakı cəm $10$-a bərabərdir, $[\mathrm{0...4}]$ aralığındakı cəm isə $15$-dir.

2. i = 1, j irəlilədə bilmirik, çünki $[\mathrm{1...4}]$ aralığının cəmi $13$-ə bərabərdir.

3. i = 2, j $[\mathrm{2...4}]$ aralığına qədər irəliləyirik.

Bütün yaxşı aralıqlar arasında maksimum dəyər $12$-dir və bu $[\mathrm{2...4}]$ aralığında əldə edilir.

Alqoritmin tətbiqi

Giriş məlumatlarını oxuyuruq.

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

Dəyişənləri eyniləşdiririk:

• $res$-də bütün işlənmiş yaxşı aralıqlardakı qiymətlərin maksimumu hesablanır;

• $s$-də mövcud $[i...j]$ aralığında olan ədədlərin cəmi saxlanılır. Mövcud $[i...j]$ aralığındakı bütün ədədlər $q$ növbəsində saxlanılır;

s = res = 0;

Otel qiymətlərini ardıcıl emal edirik.

for (i = 0; i < n; i++)
{

Mövcud otelin $val$ qiymətini oxuyuruq və növbəyə əlavə edirik.

  scanf("%d", &val);
  q.push(val);

Aralıqdakı $s$ cəmini yeniləyirik. Mövcud aralıqdakı bütün elementlər $q$ növbəsindədir.

  s += val;

Əgər mövcud aralıqdakı ədədlərin cəmi $s$ daha çoxdursa, aralığın başlanğıcındakı elementləri silirik.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

$m$-dən yüksək olmayan aralıqlardakı elementlərin cəmi arasında maksimum $res$ dəyərini hesablayırıq.

  if (s > res) res = s;
}

Cavabı çıxırıq.

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

Python tətbiqi

Növbəni elan edək.

from collections import deque
q = deque()

Giriş məlumatlarını oxuyuruq.

n, m = map(int, input().split())
costs = list(map(int, input().split()))

Dəyişənləri eyniləşdiririk:

• $res$-də bütün işlənmiş yaxşı aralıqlardakı qiymətlərin maksimumu hesablanır;

• $s$-də mövcud $[i...j]$ aralığında olan ədədlərin cəmi saxlanılır. Mövcud $[i...j]$ aralığındakı bütün ədədlər $q$ növbəsində saxlanılır;

res = s = 0

Otel qiymətlərini ardıcıl emal edirik.

for val in costs:

Mövcud otelin $val$ qiymətini növbəyə əlavə edirik.

  q.append(val)

Aralıqdakı $s$ cəmini yeniləyirik. Mövcud aralıqdakı bütün elementlər $q$ növbəsindədir.

  s += val

Əgər mövcud aralıqdakı ədədlərin cəmi $s$ daha çoxdursa, aralığın başlanğıcındakı elementləri silirik.

  while s > m:
    s -= q.popleft()

$m$-dən yüksək olmayan aralıqlardakı elementlərin cəmi arasında maksimum $res$ dəyərini hesablayırıq.

  if s > res: res = s

Cavabı çıxırıq.

print(res)