Cześć mam takie zadanie
Wyścig Tour de Bajtocja jest organizowany co roku na trasie z miasta A do miasta B. Ze względu na dziurę budżetową, w tym roku wyścig odbędzie się tylko na pewnym odcinku trasy. Nie jest jeszcze ustalone, jaki to będzie odcinek, choć ustalona jest już jego długość. Na całej trasie rozstawione są znaki ograniczające prędkość jazdy. Ograniczenie obowiązuje do momentu zmiany tego ograniczenia przez inny znak. Wyścig Tour de Bajtocja znany jest z obowiązku przestrzegania ograniczeń prędkości.
Organizatorzy zastanawiają się, jaki fragment trasy (o długości ) wybrać, aby przestrzegając ograniczeń prędkości, można było go jak najszybciej przejechać.
Zostałeś poproszony o napisanie programu, który wyznaczy najkrótszy czas przejechania takiego fragmentu trasy.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite n,m oraz d (1 <= n <= 1 000 000, 1 <= m <= d <= 10^9), pooddzielane pojedynczymi odstępami, oznaczające odpowiednio liczbę znaków ustawionych na trasie, długość odcinka, na którym powinien odbyć się wyścig, oraz długość trasy z A do B.Następne wierszy zawiera opisy kolejnych znaków ustawionych na trasie. Opis znaku składa się z dwóch liczb całkowitych s,v (0 <= s <=d, 1 <= v <= 1 000 000, ), oddzielonych pojedynczym odstępem, oznaczających odpowiednio odległość -tego znaku od miasta A oraz ograniczenie prędkości obowiązujące od ustawienia tego znaku. Możesz założyć, że 0 = s1 < s2 < ... < sn.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę rzeczywistą zaokrągloną do dokładnie trzech cyfr po kropce dziesiętnej, oznaczającą najkrótszy możliwy czas przejechania trasy długości . Wybierany odcinek trasy nie może wykraczać poza trasę z miasta A do miasta B.
No i znalazłem taką odpowiedź:
Zauważmy, że jedyne fragmenty trasy, które warto rozpatrywać, to te, które kończą się lub rozpoczynają w miejscu zmiany ograniczenia prędkości. Faktycznie, rozważmy fragment, który nie zaczyna ani nie kończy się w miejscu ustawienia znaku. Wtedy jeśli ograniczenie prędkości na jednym kawałku jest mniejsze niż na drugim, to możemy przesuwać fragment, poprawiając czas przejechania trasy. Jeśli natomiast ograniczenie prędkości jest takie same, to przesuwając fragment w jedną ze stron, nie pogorszymy czasu przejechania tego fragmentu, a będzie się on zaczynał lub kończył w miejscu ustawienia znaku.
Początki wszystkich fragmentów możemy wyznaczyć podczas w czytywania danych. Pseudokod ich wyznaczenia może wyglądać następująco.
wczytaj(n, m, d);
for i := 1 to n do begin
wczytaj(s, v);
if s - m > 0 then
nowyPoczatek(s - m);
if s + m < d then
nowyPoczatek(s);
end;
// dodajemy fragment, który kończy się w miejscu zakończenia całej trasy
nowyPoczatek(d - m);
Aby móc efektywnie rozwiązać zadanie, powinniśmy uporządkować niemalejąco początki tras. Można je posorto-wać sortowaniem szybkim w czasie
O(n log n) lub zauważyć, że powstaną nam dwa posortowane ciągi, które możemy scalić w czasie O (n).
Mając posortowany ciąg wszystkich początków fragmentów tras, możemy przejść do obliczania wyniku. Zrobimy to podobnie jak w rozwiązaniu powolnym — do obliczania czasu pomiędzy dwoma fragmentami wykorzystamy powtarzające się fragmenty tras (odejmując początek i dodając koniec). Należy tylko skakać o większe fragmenty — do wyznaczonych początków tras. Dopracowanie szczegółów technicznych tego skakania pozostawiamy Czytelnikowi. Złożoność takiego rozwiązania jest liniowa. Wszystkich początków tras będzie maksymalnie 2n, więc przeglądając tylko takie fragmenty i uaktualniając je w czasie stałym, ma
my liniowy czas rozwiązania całego rozwiązania.
No i stworzyłem taki kod:
#include "bits/stdc++.h"
using namespace std;
//struktura na dane
struct przedzial{
int pred;
int poc;
int kon;
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
//wczytujemy dane
int n, m, d, dlug, j;
cin >> n >> m >> d;
vector<przedzial> znaki(n);
cin >> znaki[0].poc >> znaki[0].pred;
for (int i = 1; i < n; i++){
cin >> znaki[i].poc >> znaki[i].pred;
znaki[i-1].kon = znaki[i].poc;
}
znaki[n-1].kon = d;
double wynik, akt;
akt = 0.0;
wynik = 99999999999999;
for (int i = 0; i < n; i++){
if (znaki[i].poc + m < d){ //jesli mozemy utworzyc droge idac do przodu
akt = 0.0;
dlug = m;
j = i;
while (dlug > 0 && dlug - (znaki[j].kon - znaki[j].poc) > 0){ //dopoki nie osiagniemy odpowiedniej dlugosci
akt += (1.0 / znaki[j].pred) * (znaki[j].kon - znaki[j].poc);
dlug -= (znaki[j].kon - znaki[j].poc);
j++;
}
akt += (1.0 / znaki[j].pred) * dlug; //dodajemy tak zeby mieć odpowiednią dlugosc
wynik = min(wynik, akt);
}
if (znaki[i].poc - m >= 0){ //jesli mozemy utworzyc drogę cofając się
akt = 0.0;
dlug = m;
j = i - 1;
while (dlug > 0 && dlug - (znaki[j].kon - znaki[j].poc) > 0){ //dopoki nie osiagniemy odpowiedniej dlugosci
akt += (1.0 / znaki[j].pred) * (znaki[j].kon - znaki[j].poc);
dlug -= (znaki[j].kon - znaki[j].poc);
j--;
}
akt += (1.0 / znaki[j].pred) * dlug; //dodajemy tak zeby mieć odpowiednią dlugosc
wynik = min(wynik, akt);
}
}
cout << fixed << setprecision(3) << wynik;
return 0;
}
Niestety jest tutaj błąd, w niektórych testach nawet wynik pozostaje bez ruszenia pomoże mi ktoś znaleźć błąd?