Runda 20 [Basic] - Samolot

17.05.2011 - Damian Rusak
Trudność

 

Zadanie tygodnia

runda 20; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB


Samolot

Nadszedł czas, aby drogą powietrzną dostarczyć ważne przesyłki na wiele lotnisk w okolicy. Samolot musi zatrzymać się na każdym z $ n $ lotnisk. Każdemu z nich przypisujemy liczbę $ B_{i} $ - oznaczającą wysokość położenia lotniska nad powierzchnią morza. Samolot ma wbudowany ultranowoczesny napęd hipertermojądrowy i nie przejmujemy się odległością jaką ma do pokonania - problematyczna za to jest zmiana jego wysokości - zatem koszt przelecenia z lotniska do lotniska to wartość bezwzględna z różnicy wysokości im przypisanych (zatem koszt przelotu między lotniskiem $ i $ oraz $ j $ to $ |B_{i}-B_{j}| $).

Możemy lecieć od dowolnego lotniska do dowolnego innego, dostajemy jednak polecenie, z którego lotniska należy rozpocząć. Czy potrafisz dla każdego takiego polecenia stwierdzić, jaki będzie najmniejszy koszt trasy, która przejdzie przez każde z lotnisk (lotnisko startowe uznajemy za "zaliczone")?

Wejście:

Pierwsza linia wejścia zawiera jedną linię zawierającą liczbę $ n $ - liczbę lotnisk. ($ 1 \leq n \leq 400000 $). W kolejnej linii znajduje się $ n $ liczb całkowitych $ B_{1} $, $ B_{2} $, ..., $ B_{n} $ - wysokości nad poziomem morza kolejnych lotnisk. ($ 1 \leq B_{i} \leq 10^{6} $). W kolejnej linii znajduje się liczba $ k $ - liczba poleceń. ($ 1 \leq k \leq 15000 $). W kolejnych $ k $ liniach znajdują się liczby $ a_{j} $ - numery miast, z których należy rozpocząć podróż.

Wyjście:

Dla każdego polecenia należy wypisać jedną liczbę całkowitą - koszt najtańszej trasy, przechodzącej choć raz przez każde lotnisko.

Przykład:

Wejście:

4
3 8 7 2
2
4
3

Wyjście:

6
7

Wyjaśnienie: pierwszy koszt daje nam przelot między miastami 4 -> 1 -> 3 -> 2, płacimy kolejno $ |2-3| $, $ |3-7| $, $ |7-8| $, łącznie $ 6 $. Dla drugiego zapytania optymalna trasa to 3->2->1->4.

 

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com