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 баллов. Примеры Ввод Вывод Пояснение 5 1 2 3 1 100 4 У Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже: 1. Удалим последний файл. Это займет одну секунду. 2. Затем удалим файл размера 2 за одну секунду. 3. Далее удалим файл размера 3 за одну секунду. 4. Теперь удалим любой из оставшихся двух файлов за одну секунду. 5. Последний файл моментально удалится сам. Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды. 1 1 0 У Сергея изначально есть всего один файл, который сразу же удалится.

Answer 1

Ответ:

n = int(input())

min = 10**5

for i in range(n):

   element = int(input())

   if element < min:

       min = element

print((n-1) * min)

Пошаговое объяснение:

Язык python 3, самое быстрое решение без массивов и долгих поисков. Берём и удаляем все элементы всегда возле самого минимального числа.

Answer 2

Ответ:

n = int(input())

ints = []

for i in range(n):

ints.append(int(input()))

min_val = min(ints)

print(min_val * (n - 1))

Берем минимальное число из списка и удаляем все числа рядом с ним. Это будет минимальное время

Answer 3

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

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

Алгоритм будет выглядеть следующим образом:

1. Отсортируем файлы по размеру.
2. Инициализируем переменную total_time = 0 для подсчета общего времени.
3. Если N = 1 (только один файл), то total_time = a1 (время удаления единственного файла) и выходим из алгоритма.
4. Если N > 1, то выполним следующий цикл:
   • Удаляем файл с наименьшим размером (первый файл в отсортированном списке) и увеличиваем total_time на его размер.
   • Обновляем размеры оставшихся файлов:
     • Для второго файла: a2 = a2 - a1.
     • Для последнего файла: aN = aN - aN-1.
     • Для всех остальных файлов: ai = ai - min(ai-1, ai+1).
   • Обновляем N = N - 1 (уменьшаем количество файлов на 1).
   • Если N = 1, то total_time = total_time + a1 (добавляем время удаления последнего файла) и выходим из алгоритма.
5. Выводим total_time.

Применим данный алгоритм к примеру из условия:

Входные данные: 5 1 2 3 1 100

Шаг 1: Отсортированный список размеров файлов: [1, 1, 2, 3, 100]

Шаг 2: total_time = 0

Шаг 3: N > 1, продолжаем выполнение алгоритма

Шаг 4:

• Удаляем файл с размером 1: total_time = 1, осталось [1, 2, 3, 100]
• Обновляем размеры оставшихся файлов: [1, 1, 2, 100]
• N = 4

Шаг 4:

• Удаляем файл с размером 1: total_time = 2, осталось [1, 2, 100]
• Обновляем размеры оставшихся файлов: [1, 1, 100]
• N = 3

Шаг 4:

• Удаляем файл с размером 1: total_time = 3, осталось [1, 100]
• Обновляем размеры оставшихся файлов: [1, 99]
• N = 2

Шаг 4:

• Удаляем файл с размером 1: total_time = 4, остался [100]
• Обновляем размеры оставших