Решение с использование "ЦЕНТРА ТЯЖЕСТИ"
1. Считаем значение доставки из отметки 0, которое делим на общее число посылок. Это некоторый аналог требуемого положения.
2. Находим соседний телескоп (справа)
3.. От найденного положения находим локальный минимум
Временные характеристики:
для файла В работа меньше 200 секунд, смещение оценки 400 позиций из 1100000
#z27-6638 использование центра масс
from time import time
def fff(n): # вычисление стоимости доставки для всех пунктов, описание в DD
# n - планируемое расположение приемника
r=0
for d in DD:
x,y=d[0],d[1] # x - расстояние, у - кол-во посылок
r+=abs(n-x)*y # стоимость = расстояние * кол-во
return r # r - общая стоимость доставки
tm=time()
#f=open('27B_6638.txt') #имена файлов с данными
f=open('27A_6638.txt')
N=int(f.readline()) # число записей с пунктами
DD=[] # список для данных
sp=0 # общее кол-во "посылок"
v=100 # максимальный объём посылки
for _ in range(N):
km,d=map(int,f.readline().split()) # км локатора, кол-во измерений
p=(d-1)//v+1 # кол-во посылок
sp+=p # подсчёт суммарного числа посылок
DD.append((km,p)) # обновление данных
f.close() # окончание ввода данных
print('чтение завершено:',time()-tm)
ss=fff(0) # вычисление значения для начальной точки
ms=ss/sp # !!! условный центр масс
print(N,ss,sp,ms) # промежуточная печать
k=0 # место для точки отсчёта
while DD[k][0]<ms :k+=1 # DD[k] место первого правого приемника
km=DD[k][0] # начальное расположение пункта сбора
rez,rr,ri=km,fff(km),k # фиксация начальных значений поиска
print(rez,rr,ri) # печать найденных значений
go =True
j=k
while go : # поиск влево от k
j-=1 # место
km=DD[j][0] # положение
r=fff(km) # значение
if r<=rr : # сравнение и фиксация результатов (налево <=)
rez,rr,ri=km,r,j
else : go=False # пошло возрастание
print('*',rez,rr,ri,'time=',time()-tm) # печать промежуточных результатов
go =True
j=k
while go : # поиск направо от k
j+=1 # место
km=DD[j][0] # положение
r=fff(km) # значение
if r<rr : # сравнение и фиксация результатов (направо строго <)
rez,rr,ri=km,r,j
else : go=False # пошло возрастание
print('rez=',rez,rr,ri,'time=',time()-tm)
#rez - положение пункта сбора, rr - общая стоимость доставки, ri - порядковый номер
