Башня

@gurulTailan · 11.07.2020, 12:02. **Показов** 42567. **Ответов** 109

Студворк — интернет-сервис помощи студентам

Вот сейчас думаю, не могу решить следующую задачу:
Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
Входные данные
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).
Выходные данные
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

Ввод
8 3
1 2 3 4 1 6 7 8
вывод
2
2 6

ввод
1 1
1
вывод
1
1

ПОМОГИТИ РЕШИТЬ ЗА ВРЕМЯ O(n)
Я начал делать, но не могу понять, как быстро выбрать башни для защиты королевства:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def push(stack, elem):
    stack.append(elem)
    return elem
def top(stack):
    return stack[-1]
def pop(stack):
    return stack.pop()
def size(stack):
    return len(stack)
def power(a, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power(a * a, n // 2)
    else:
        return power(a, n - 1) * a
inf = 2 * power(10, 9) + 1
n, k = map(int, input().split())
a = [-inf] + list(map(int, input().split())) + [-inf]
p = [0] * (n + 2)
for i in range(1, n + 1):
    p[i] = p[i - 1] + a[i]
p[-1] = p[-2]
stack = []
push(stack, 0)
ans = [0] * (n + 2)
for i in range(n + 2):
    while a[top(stack)] > a[i]:
        ans[pop(stack)] = i
    push(stack, i)
imin = 1
res = [0] * (n - k + 2)
for i in range(1, n - k + 2):
    if imin < i:
        imin = i
    while ans[imin] < i + k:
        imin = ans[imin]
    res[i] = a[imin] * (p[i + k - 1] - p[i - 1])
 
#https://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3583#1

@Angrey_p · 14.07.2020, 14:42

Alex_qd, да

@Kkkkkkkk · 14.07.2020, 15:57

Ну что у кого нибудь получилось?

@Gdez · 14.07.2020, 16:29

Башня да
Выложено

@Kkkkkkkk · 14.07.2020, 16:36

Gdez, я про сосуды

@weatherReport · 14.07.2020, 18:24

https://znanija.com/task/37797019

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
 
n, k = map(int, input().split())
x, d, ssum = list(map(int, input().split())), deque(), 0
b = [(0, 0) for i in range(n)]
for i in range(n):
    ssum += x[i]
    if i >= k:
        ssum -= x[i - k]
        if d[0] == i - k:
            d.popleft()
    while len(d) and x[d[-1]] >= x[i]:
        d.pop()
    d.append(i)
    if i >= k - 1:
        nb = (b[i - k][0] + x[d[0]] * ssum, i - k + 2)
        b[i] = max(b[i - 1], nb, key=lambda x: x[0])
 
i = n - 1
d = deque()
j = b[-1][1]
d.appendleft(j)
while i != 0:
    i -= 1
    j1 = b[i][1]
    if j - k >= j1 and j1 > 0:
        d.appendleft(j1)
        j = j1
print(str(len(d)))
print(" ".join(map(str, d)))

@Russia_top · 14.07.2020, 19:54

Gdes, ваш код на Сириусе прошёл, спасибо!

Добавлено через 5 минут
Рабочее решение по сосудам!!! На Сириусе прошло.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from math import fabs
 
NN = 1000000
eps = 1e-7
h = [0 for _ in range(NN)]
 
def get_h():
    global a, h, s
    assert (s < t)
    return a[h[s]]
 
 
def pop_h():
    global s, h
    assert (s < t)
    s += 1
    return h[s - 1]
 
 
def push_h(x):
    global t, h, s, a
    while s < t and a[h[t - 1]] < a[x]:
        t -= 1
    h[t] = x
    t += 1
 
 
n, C = str(input()).split()
n = int(n)
C = float(C)
a = [0 for _ in range(NN)]
for i in range(n - 1):
    a[i] = int(input())
p = [0 for i in range(n)]
s = 0
t = 0
i = 0
j = 1
l = C
r = 0
push_h(0)
while j < n and i < j  and l > (a[j - 1] + eps):
    ev1 = (l - r) * (j - i) / (j - i + 1)
    if s < t:
        ev2 = (l - get_h()) * (j - i)
        ev = min(ev2, ev1)
    else:
        ev = ev1
    l -= (ev / (j - i))
    r += ev
    if fabs(l - r) < eps:
        push_h(j)
        j += 1
        r = 0
    if fabs(l - get_h()) < eps:
        x = pop_h()
        while i <= x:
            p[i] = l
            i += 1
        i = x + 1
    if (i == j) or (l < a[j - 1] + eps):
        while i < j:
            p[i] = l
            i += 1
        l = r
        r = 0
        i = j
        push_h(j)
        j += 1
while i < j:
    p[i] = l
    i += 1
for i in range(n):
    print(p[i])

@Roket_Flame · 14.07.2020, 21:17

Пожалуйста, отправь код в приемлимом виде, или хотя бы отступы как-нибудь покажи

@Gdez · 14.07.2020, 21:41

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from math import fabs
 
NN = 1000000
eps = 1e-7
h = [0 for _ in range(NN)]
 
def get_h():
global a, h, s
assert (s < t)
return a[h[s]]
 
 
def pop_h():
global s, h
assert (s < t)
s += 1
return h[s - 1]
 
 
def push_h(x):
global t, h, s, a
while s < t and a[h[t - 1]] < a[x]:
t -= 1
h[t] = x
t += 1
 
 
n, C = str(input()).split()
n = int(n)
C = float(C)
a = [0 for _ in range(NN)]
for i in range(n - 1):
a[i] = int(input())
p = [0 for i in range(n)]
s = 0
t = 0
i = 0
j = 1
l = C
r = 0
push_h(0)
while j < n and i < j and l > (a[j - 1] + eps):
ev1 = (l - r) * (j - i) / (j - i + 1)
if s < t:
ev2 = (l - get_h()) * (j - i)
ev = min(ev2, ev1)
else:
ev = ev1
l -= (ev / (j - i))
r += ev
if fabs(l - r) < eps:
push_h(j)
j += 1
r = 0
if fabs(l - get_h()) < eps:
x = pop_h()
while i <= x:
p[i] = l
i += 1
i = x + 1
if (i == j) or (l < a[j - 1] + eps):
while i < j:
p[i] = l
i += 1
l = r
r = 0
i = j
push_h(j)
j += 1
while i < j:
p[i] = l
i += 1
for i in range(n):
print(p[i])

Добавлено через 1 минуту

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from math import fabs
 
NN = 1000000
eps = 1e-7
h = [0 for _ in range(NN)]
 
def get_h():
    global a, h, s
    assert (s < t)
    return a[h[s]]
 
 
def pop_h():
    global s, h
    assert (s < t)
    s += 1
    return h[s - 1]
 
 
def push_h(x):
    global t, h, s, a
    while s < t and a[h[t - 1]] < a[x]:
        t -= 1
    h[t] = x
    t += 1
 
 
n, C = str(input()).split()
n = int(n)
C = float(C)
a = [0 for _ in range(NN)]
for i in range(n - 1):
    a[i] = int(input())
p = [0 for i in range(n)]
s = 0
t = 0
i = 0
j = 1
l = C
r = 0
push_h(0)
while j < n and i < j  and l > (a[j - 1] + eps):
    ev1 = (l - r) * (j - i) / (j - i + 1)
    if s < t:
        ev2 = (l - get_h()) * (j - i)
        ev = min(ev2, ev1)
    else:
        ev = ev1
    l -= (ev / (j - i))
    r += ev
    if fabs(l - r) < eps:
        push_h(j)
        j += 1
        r = 0
    if fabs(l - get_h()) < eps:
        x = pop_h()
        while i <= x:
            p[i] = l
            i += 1
        i = x + 1
    if (i == j) or (l < a[j - 1] + eps):
        while i < j:
            p[i] = l
            i += 1
        l = r
        r = 0
        i = j
        push_h(j)
        j += 1
while i < j:
    p[i] = l
    i += 1
for i in range(n):
    print(p[i])

Добавлено через 1 минуту
Это
Сообщающиеся сосуды

@Roket_Flame · 14.07.2020, 22:08

Спасибо!

@Nebobo · 02.08.2021, 20:10

всем привет, есть вот такое решение. почему-то ругается на формат вывода. Представить себе не могу, как тут можно неправильно выводить...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from collections import deque
 
 
def min_tower(arr, n, k):
    d = deque()
    res = []
    summ = sum(arr[:k])
    temp = arr[0]
    for i in range(n):
        if i + k < n:
            summ = summ - temp + arr[i + k]
            temp = arr[i]
        if i >= k and d[0] == i - k:
            d.popleft()
        while len(d) and arr[d[-1]] >= arr[i]:
            d.pop()
        d.append(i)
        if i >= k - 1:
            res.append(arr[d[0]] * summ)
    return res
 
 
n, k = map(int, input().split())
nums = [int(i) for i in input().split()]
sums = [0] + min_tower(nums, n, k)
 
best = [0]
temp = ['']
 
 
for i in range(1, n - k + 2):
    if i >= k:
        best.append(best[-k] + sums[i])
        temp.append(temp[-k] + str(i) + ' ')
    else:
        best.append(sums[i])
        temp.append(str(i) + ' ')
    if best[i] <= best[i - 1]:
        best[i] = best[i - 1]
        temp[i] = temp[i - 1]
 
print(len(temp[-1]) // 2)
print(temp[-1].strip(' '))

Добавлено через 1 минуту
Была также попытка решить в один проход - та же проблема.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque
n, k = map(int, input().split())
nums = list(map(int, input().split()))
d = deque()
summ = sum(nums[:k - 1])
j = - k
dp_z = [0]
dp_t = ['']
for i in range(n):
    j += 1
    if i > k and d[0] == i - k:
        d.popleft()
    while d and nums[d[-1]] >= nums[i]:
        d.pop()
    d.append(i)
    if i >= k - 1:
        summ += nums[i]
        '''print(summ * nums[d[0]])'''
        if j >= k:
            if (summ * nums[d[0]] + dp_z[-k]) > dp_z[-1]:
                dp_z.append(dp_z[-k] + summ * nums[d[0]])
                dp_t.append(dp_t[-k] + ' ' + str(j + 1))
            else:
                dp_z.append(dp_z[-1])
                dp_t.append(dp_t[-1])
        else:
            if summ * nums[d[0]] > dp_z[-1]:
                dp_z.append(summ * nums[d[0]])
                dp_t.append(str(j + 1))
            else:
                dp_z.append(dp_z[-1])
                dp_t.append(dp_t[-1])
        summ = summ - nums[j]
print((len(dp_t[-1]) + 1) // 2)
print(dp_t[-1])

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

@Angrey_p 0 / 0 / 0 Регистрация: 12.07.2020 Сообщений: 19
	14.07.2020, 14:42
	Alex_qd, да 0

@Kkkkkkkk 6 / 6 / 0 Регистрация: 25.06.2020 Сообщений: 14
	14.07.2020, 15:57
	Ну что у кого нибудь получилось? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	14.07.2020, 16:29
	Башня да Выложено 0

@Kkkkkkkk 6 / 6 / 0 Регистрация: 25.06.2020 Сообщений: 14
	14.07.2020, 16:36
	Gdez, я про сосуды 0

@Roket_Flame 8 / 7 / 1 Регистрация: 15.05.2020 Сообщений: 10
	14.07.2020, 21:17
	Пожалуйста, отправь код в приемлимом виде, или хотя бы отступы как-нибудь покажи 0

@Roket_Flame 8 / 7 / 1 Регистрация: 15.05.2020 Сообщений: 10
	14.07.2020, 22:08
	Спасибо! 0