Форум » Обработка числовых последовательностей » Задача 27 6041 » Ответить
Задача 27 6041
MercuL`: Добрый день возникла проблема с решением 27-ой задачи. Условие: На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до ближайшего центра переработки. На автодороге расположено два центра переработки отходов, каждый в одном из пунктов сбора мусора. Расстояние между центрами переработки одинаково, независимо от направления движения по кольцевой автодороге. Центры переработки расположены таким образом, что общая стоимость доставки мусора из всех пунктов минимальна. Определите минимальную суммарную стоимость доставки мусора из всех пунктов сбора в центры переработки отходов. Код немнго запутанный, но попытался комментариями оьхяснить свою логику, в итоге сделал следующим образом: [pre2]file = open('27-130a.txt') n = int(file.readline()) points = [int(i) for i in file] sum_ = 0 min_sum = 10 ** 10 pluses = minuses = 0 new_sum = 0 for i in range(1, (n - 2) // 4 + 1): sum_ = sum_ + points[ i] * i + points[-i] * i + points[n // 2 + i] * i + points[n // 2 - i] * i #Считаем сумму для расположения на нулевом и n//2 элементе (диаметрально противоположном) minuses = minuses + points[ i] + points[n // 2 + i] # изменяем "минусы" - те элементы, стоимость вывоза из котрых при перемещении пунктов сбора уменьшилась pluses = pluses + points[-i + 1] + points[n // 2 - i + 1] # аналогично с "плюсами" for k in range(1, n // 4): minuses = minuses - points[k] + points[n//2+k] # пересчитывем "плюсы" и "минусы" для каждого положения центров minuses = minuses + points[(n - 2) // 4 + k] + points[n//2+(n-2)//4+k] pluses = pluses + points[k] + points[n//2+k] minuses = minuses - points[(n - 2) // 4 + k] - points[n // 2 + (n - 2) // 4 + k] new_sum = sum_ + pluses - minuses min_sum = min(min_sum, new_sum) print(min_sum)[/pre2] Ответы получаются отдаленно похожие, но все-таки совсем не те: 73776 и 1867315141 вместо 69572 и 1861699580. Прошу, помогите найти ошибку или продемонстрируйте альтернативное решение.
Ответов - 1
MercuL`: Вот правильное решение. [pre2] file = open('27-130a.txt') n = int(file.readline()) points = [int(i) for i in file] sum_ = 0 min_sum = 10 ** 10 pluses = minuses = 0 new_sum = 0 for i in range(1, (n - 2) // 4 + 1): sum_ = sum_ + points[ i] * i + points[-i] * i + points[n // 2 + i] * i + points[n // 2 - i] * i minuses = minuses + points[ i] + points[n // 2 + i] pluses = pluses + points[-i + 1] + points[n // 2 - i + 1] print(pluses, minuses, sum_) for k in range(1, n // 2): sum_ = sum_ - minuses + pluses min_sum = min(min_sum, sum_) minuses = minuses + points[(n-2)//4+k] + points[(n//2 + (n-2)//4+k)%n] pluses = pluses + points[k] + points[n//2+k] minuses = minuses - points[k] - points[n//2+k] pluses = pluses - points[(n-2)//4+k+1] - points[(n//2 + (n-2)//4+k+1)%n] print(min_sum) [/pre2]
полная версия страницы