Автобус (Время: 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 на втором тесте