Сумма разбросов для всех подотрезков заданной последовательности

@hiz · Регистрация: 25.10.2022

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

Назовем разбросом последовательности чисел разницу между максимальным и минимальным значением в этой последовательности. Для последовательности 3, 5, 7, 4 разброс будет равен 4 (7 - 3), а для последовательности 17, 17 разброс будет равен 0 (17 - 17).

Найдите сумму разбросов для всех подотрезков заданной последовательности. Подотрезком называется последовательность подряд идущих элементов.

Формат входных данных
В первой строке вводится число n (2 ≤ n ≤ 300000) - длина последовательности.

В следующих n строках вводятся числа ai (1 ≤ ai ≤ 108) - элементы последовательности.

Формат результата
Выведите ответ на задачу.

Примеры
Входные данные
3
1
2
3
Результат работы
4
Входные данные
4
7
5
7
5
Результат работы
12
Входные данные
4
3
1
7
2
Результат работы
31
Примечания
Подотрезки длины 1 дают разброс, равный нулю.

В первом примере подотрезки (1, 2), (2, 3) и (1, 2, 3) дают разброс 1, 1 и 2 соответственно. Сумма равна 4.

Во втором примере следующие отрезки и соответствующие им разбросы:

(7, 5) - 2, (5, 7) - 2, (7, 5) - 2, (7, 5, 7) - 2, (5, 7, 5) - 2, (7, 5, 7, 5) - 2

Сумма разбросов равна 12.

Система оценки:

Решения, верно работающие при n ≤ 3000 будут получать не менее 40 баллов.

@Pythonistj · 27.11.2022, 13:00

Python
1
2
3
4
5
6
a = int(input())
b = []
for i in range(a):
    c = int(input())
    b.append(c)
print(max(b) + min(b))

@lynnikae · 27.11.2022, 13:02

Есть решение, но подошло только по двум вариантам
может кто-то успеет доделать)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import itertools
 
 
n = int(input())
posled = []
for i in range(n):
    posled.append(input())
p = ''.join(posled)
ver = []
combs = []
for l in range(1, len(p) + 1):
    combs.append(list(itertools.combinations(p, l)))
for c in combs:
    for t in c:
        ver.append("".join(t))
summ = 0
for i in range(len(ver)):
    if (ver[i] in p) and (len(ver[i]) != 1):
        curr = [int(i) for i in ver[i]]
        summ += max(curr) - min(curr)
print(summ)

@durt · 04.09.2023, 01:42

Данная задача решается с помощью стеков рекордов. Необходимо найти разность суммы максимумов и суммы минимумов по всем подотрезкам массива. https://peltorator.ru/posts/stack-of-records/

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@hiz 0 / 0 / 0 Регистрация: 25.10.2022 Сообщений: 4

	Сумма разбросов для всех подотрезков заданной последовательности 27.11.2022, 10:44. Показов 2910. Ответов 3 Метки нет (Все метки) Назовем разбросом последовательности чисел разницу между максимальным и минимальным значением в этой последовательности. Для последовательности 3, 5, 7, 4 разброс будет равен 4 (7 - 3), а для последовательности 17, 17 разброс будет равен 0 (17 - 17). Найдите сумму разбросов для всех подотрезков заданной последовательности. Подотрезком называется последовательность подряд идущих элементов. Формат входных данных В первой строке вводится число n (2 ≤ n ≤ 300000) - длина последовательности. В следующих n строках вводятся числа ai (1 ≤ ai ≤ 108) - элементы последовательности. Формат результата Выведите ответ на задачу. Примеры Входные данные 3 1 2 3 Результат работы 4 Входные данные 4 7 5 7 5 Результат работы 12 Входные данные 4 3 1 7 2 Результат работы 31 Примечания Подотрезки длины 1 дают разброс, равный нулю. В первом примере подотрезки (1, 2), (2, 3) и (1, 2, 3) дают разброс 1, 1 и 2 соответственно. Сумма равна 4. Во втором примере следующие отрезки и соответствующие им разбросы: (7, 5) - 2, (5, 7) - 2, (7, 5) - 2, (7, 5, 7) - 2, (5, 7, 5) - 2, (7, 5, 7, 5) - 2 Сумма разбросов равна 12. Система оценки: Решения, верно работающие при n ≤ 3000 будут получать не менее 40 баллов. 0

@durt 5 / 5 / 0 Регистрация: 30.08.2022 Сообщений: 21
	04.09.2023, 01:42
	Данная задача решается с помощью стеков рекордов. Необходимо найти разность суммы максимумов и суммы минимумов по всем подотрезкам массива. https://peltorator.ru/posts/stack-of-records/ 0