0

Автобус (Время: 1 сек. Память: 16 Мб Сложность: 39%) Василий работает водителем автобуса, и у него есть по-настоящему тяжелая работа: он перевозит пассажиров из пункта A в пункт B. При этом он должен выполнять свою работу безопасно и как можно быстрее. Кроме того, каждый водитель должен повиноваться дорожным правилам и нормам, иначе, он будет оштрафован местной полицией.

Маршрут Василия состоит из N отрезков, которые он проезжает последовательно, начиная от 1-го и завершая N-м отрезком. У каждого отрезка задана длина в километрах Di.

Конечно, на маршруте Василия есть ограничения скорости. У каждого отрезка есть свое собственное ограничение скорости Li км/ч. В случае превышения скорости на i-м отрезке, водитель автобуса будет немедленно остановлен полицейским, который потратит Hi часов на заполнение соответствующих бумаг. Водитель не может быть остановлен более одного раза на каждом отрезке.

Автобус едет вдоль маршрута с постоянной скоростью S, которую Василий выбирает в начале маршрута (в пункте A). Автобус не может превышать максимальную конструктивную скорость, которая определена значением M км/ч.

Пожалуйста, помогите Василию выбирать правильную скорость, чтобы достигнуть конечного пункта B как можно быстрее.

Входные данные: Первая строка входного файла INPUT.TXT содержит два числа, разделенные пробелом: количество отрезков N (N ≤ 1000) в маршруте Василия и максимально возможную конструктивную скорость автобуса M (M ≤ 105). Далее идут N строк, в каждой из которых определены разделенные пробелом значения Di, Li и Hi, описывающие i-й отрезок пути (Di, Hi ≤ 1000, Li ≤ 105). Все числа, определенные во входных данных натуральные.

Выходные данные: В выходной файл OUTPUT.TXT выведите оптимальную скорость автобуса. В случае неоднозначного ответа следует выбрать наибольшее значение. Моя суть решения использовать бинарный поиск по производной функции. Асимптотика O(n*log(m)) Код на Python:

def f(v):
    s = 0
    for i in arr:
        if v > i[1]:
            s += i[2]
        s += i[0] // v
    return s


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
l, r = 0, m + 1
while r - l > 1:
    mid = (r + l) // 2
    if f(mid - 1) >= f(mid):
        l = mid
    else:
        r = mid
print(l)

Код на C++:

#include<iostream>
#include<vector>
using namespace std;

struct Third {
    int d, l, h;
};

int n, m, di, li, hi, mid, l, r;
vector<Third> a(0);


long f(int v) {
    long s = 0;
    for (Third x : a) {
        if (v > x.l) {
            s += (long)x.h;
        }
        s += (long)((x.d - 1) / v + 1);
    }
    return s;
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> di >> li >> hi;
        Third road_i;
        road_i.d = di;
        road_i.l = li;
        road_i.h = hi;
        a.push_back(road_i);
    }
    l = 0, r = m + 1;
    while (r - l > 1) {
        mid = (r + l) / 2;
        if (f(mid - 1) >= f(mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    cout << l;
    return 0;
}

Как я понял, нам нужно найти минимум унимодальной функции, в этом и заключается суть моего решения. оба решение получают WA на втором тесте

10
  • опиши словами свое решение
    – Grundy
    Commented 26 окт. 2023 в 8:35
  • бинарный поиск по производной функции, одно из решений, как можно найти минимум унимодальной функции, делю массив на две части и смотрю, функция возрастает, или убывает, если возрастает, то надо отсечь правую сторону, если убывает, то надо отсечь левую сторону Commented 26 окт. 2023 в 8:40
  • Функция явно не унимодальна. Для каждого отрезка получается убывание-скачок-ещё убывание, сумма времён по отрезкам будет со многими максимумами
    – MBo
    Commented 26 окт. 2023 в 8:42
  • @MBo, я не понимаю как вы считаете все :-D учитывается, что в зависимости от выбранной скорости участок может быть как медленнее так и быстрее?
    – Grundy
    Commented 26 окт. 2023 в 8:44
  • это я уже понял, когда нарисовал эту функцию. подскажите решение? сейчас на уме только проход по всем возможным скоростям, но это валится так же на втором тесте Commented 26 окт. 2023 в 8:45

2 ответа 2

2

Заметим что для скорости v время прохожения маршрута равно (∑di) / v + ∑i:li<v hi. Первое слагаемое - время в движении. Второе слагаемое - сумма штрафов. Во втором случае суммирование ведётся только по тем i для которых li < v. Ясно что имеет смысл рассматривать только скорости равные одному из li или m. Двигаться медленее чем позволяют шрафы или конструкция автобуса значит потратить больше времени чем возможно.

В дальнейшем предполагаем что все отрезки упорядочены по "штрафной" скорости. Первое слагаемое вычисляется одним делением, если заранее сосчитать полную длину маршрута. Второе слагаемое на следующем отрезке увеличивается на hi - штраф текущего отрезка. Тут есть тонкость, если "штрафные" скорости равны на отрезках, но она не повлияет на результат.

Просмотр отрезков нужно прервать если очередная "штрафная" скорость сравнялась или превысила максимальную скорость автобуса. Максимальная скорость автобуса тоже проверяется.

Сложность алгоритма O(nlogn) - время тратится на сортировку. Затем за линейное время вычисляются времена прохождения маршрута.

import fractions
 
n, m = map(int, input().split())
 
r = sorted(
    (tuple(map(int, input().split())) for _ in range(n)),
    key=lambda t: t[1]
)
 
length = sum(di for di, _, _ in r)
 
best_v = 1
best_t = length
 
sum_hi = 0
for _, li, hi in r:
    if li >= m:
        break
    t = fractions.Fraction(length, li) + sum_hi
    if t <= best_t:
        best_v = li
        best_t = t
 
    sum_hi += hi
 
t = fractions.Fraction(length, m) + sum_hi
if t <= best_t:
    best_v = m
    best_t = t
 
print(best_v)
1

нам нужно пройтись по всем ограничениям скоростей+ограничение самого автобуса и посчитать для них, сколько они будут идти от A до B и выбрать из этого минимум.

def f(v):
    s = 0
    for i in arr:
        if v > i[1]:
            s += i[2]
        s += i[0] / v
    return s


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]
arr.append([0, m, m])
min_t, min_v = int(1e10), 0
for i in range(n + 1):
    if arr[i][1] > m: continue
    pret_min_t = f(arr[i][1])
    if min_t > pret_min_t or (min_t == pret_min_t and min_v < arr[i][1]):
        min_t, min_v = pret_min_t, arr[i][1]
print(min_v)

асимптотика: O(n^2) ~1e6 операций

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.