Задача D. Проект "Ровные дороги" - 2

@Angrey_p · Регистрация: 12.07.2020

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

Задача D. Проект "Ровные дороги" 2
При проектировании новой автодороги было принято решение сделать её не более чем из двух абсолютно горизонтальных участков. Будущую трассу разбили на nn равных по длине малых отрезков. Будем считать, что в пределах одного малого отрезка местность имеет одну и ту же высоту h_ih
i

. При этом в целях эффективной трансформации местности требуется для выравнивания использовать исключительно грунт с этой же трассы. Это означает, что можно с некоторого малого отрезка высоты h_ih
i

взять некоторое количество грунта dd так, что высота этого участка станет h_i - d > 0h
i

−d>0. Далее эти dd единиц грунта обязательно нужно переместить на другой малый отрезок высоты h_jh
j

так, что его высота станет h_j + dh
j

+d. Перемещать грунт можно только в пределах одного из двух выбранных участков, то есть отрезки номер ii и номер jj должны принадлежать одному и тому же горизонтальному после выравнивания участку. В данной версии задачи высоты выравниваемых участков могут быть любыми положительными, в том числе и не целыми числами. Следующим важным вопросом при строительстве являются трудозатраты. По этой причине требуется выбрать такое разбиение трассы ровно на два непустых участка, чтобы суммарный объём перемещенного грунта был минимально возможным.

Формат входных данных

В первой строке содержится число nn - количество малых отрезков, на которые разбили трассу, 2 \leq n \leq 2*10^52≤n≤2∗10
5
. Во второй строке указаны высоты h_ih
i

этих отрезков через пробел в порядке слева направо, 1 \leq h_i \leq 2*10^51≤h
i

≤2∗10
5
.

Формат выходных данных

Вывести два ненулевых числа aa и bb через пробел. Их сумма должна равняться nn. Отрезки с номерами c первого по aa-й включительно будут принадлежать первому выровненному участку, отрезки с номерами от a+1a+1 до nn будут принадлежать второму выровненному участку. При этом суммарный объём грунта, перемещенного для такого выравнивания, должен быть минимальным среди всех возможных разбиений трассы на два участка. Если минимальных вариантов несколько вывести тот, у которого число aa меньше.

Я написал полностью рабочую программу но когда отправляю ее на степик он сначала 5 минут обрабатывает, а потом выдает ошибку Checker timeout error. Первый вариант задачи я сделал с двумя вложинными for и думал проблема в этом, оптимизировал код, но все равно выдает эту же ошибку. Можите помочь пожалуйста оптимизировать этот код:

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
import numpy as np
def more_than(ar,value):
    return ar[ar>value]
 
n=int(input())
road=list(map(int,input().split()))
min=max(road)
mixed_left=0
mixed_right=0
answer=0
for i in range(1,n):
    left=road[:i]
    right=road[i:]
 
    mid_left=sum(left)/len(left)
    mid_right=sum(right)/len(right)
 
    big_left = more_than(np.array(left), mid_left)
    mixed_left=sum(big_left) - mid_left * len(big_left)
 
    big_right = more_than(np.array(right), mid_right)
    mixed_right=sum(big_right) - mid_right * len(big_right)
 
    if min>mixed_left+mixed_right:
        min=mixed_left+mixed_right
        answer=len(left)
 
    mixed_left=0
    mixed_right=0
print(answer,n-answer)

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Киев стоит - украинская песня zorxor 28.01.2026 wfWdiRqdTxc О Господи, Вечный, Ты . . . Я помоги, Бесконечный. . . Я прошу Ты. . . Я погибаю, спаси. . . Я прошу Тебя Вечный. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .