Question

Задача 7: Удаление данных Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера. На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a1, a2, ..., aN. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из ai−1 и ai+1 секунд (для удаления первого файла потребуется a2 секунд, а для удаления последнего — aN−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно. У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы. Сергей может удалять файлы последовательно в любом порядке. Входные данные В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 105) — количество файлов на компьютере шпиона. В каждой из следующих N строк записано по одному целому числу ai (1 ≤ ai ≤ 104) — размер файла с номером i на компьютере Сергея. Выходные данные В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов. Система оценки Решения, правильно работающие только для случаев, когда N не превосходит 10, будут оцениваться в 20 баллов. Решения, правильно работающие только для случаев, когда N не превосходит 1000, будут оцениваться в 60 баллов.

Answer 1

n = int(input())

ints = []

for i in range(n):

ints.append(int(input()))

min_val = min(ints)

print(min_val * (n - 1))

Answer 2

Для решения данной задачи можно использовать жадный алгоритм.

Идея состоит в том, чтобы на каждом шаге выбирать файл с минимальным размером, чтобы удалить его и уменьшить количество файлов, требующих удаления.

Вот шаги алгоритма:

1. Считать входные данные: число файлов N и размеры файлов a1, a2, ..., aN.

2. Создать переменную total_time и установить ее в 0. Эта переменная будет содержать общее время удаления файлов.

3. Пока N > 1 (т.е. остаются файлы для удаления), выполнить следующие действия:

   • Найти файл с минимальным размером min_size среди оставшихся файлов.
   • Найти индекс i этого файла в исходном списке файлов.
   • Добавить min(a[i-1], a[i+1]) к total_time.
   • Удалить файл с индексом i из списка файлов и уменьшить N на 1.

4. Добавить a[1] (размер последнего оставшегося файла) к total_time.

5. Вывести total_time.

Вот пример реализации данного алгоритма на языке Python:

pythonCopy code
N = int(input())
files = [int(input()) for _ in range(N)]

total_time = 0

while N > 1:
    min_size = min(files)
    i = files.index(min_size)
    total_time += min(files[i-1:i] + files[i+1:i+2])
    files.pop(i)
    N -= 1

total_time += files[0]
print(total_time)

Этот алгоритм имеет временную сложность O(N^2) из-за поиска минимального размера файла на каждом шаге. Если количество файлов N достаточно велико, можно использовать более эффективные структуры данных для поиска минимального значения, такие как куча (heap), чтобы снизить сложность до O(N log N).