Strona główna » Algorytmy » Artykuły » Daleka Stacja
 

Daleka Stacja

https://mattomatti.com/a0211

Zadanie

W równych odcinkach wzdłuż torów leży n miejscowości. Podana jest lista miast w których jest stacja kolejowa (nie musi być posortowana). Jaka jest największa odległość między stacją, a dowolnym miastem? Miasta indeksujemy od 0 do n - 1.

Przykład

Przypuśćmy, że wzdłuż torów leży n = 8 miejscowości. Stacje mieszczą się w miastach 2, 4 i 7 co przedstawia poniższy schemat:

W tym przypadku maksymalna odległość wynosi 2, ponieważ osoby mieszkające w miejscowości 0 najbliższą stację mają dwie miejscowości dalej. Miejscowości 1, 3, 5 oraz 6 mają stacje "po sąsiedzku" w odległości 1.

Implementacja

Analiza Zadania

W celu rozwiązania podanego problemu należy zauważyć, że najdalsza odległość pomiędzy dwoma miejscowościami to odległość pomiędzy nimi podzielona przez 2. Część ułamkowa jest odrzucana. Jednak dla pierwszej i ostatniej miejscowości należy brać pełną odległość do najbliższej stacji.

Rozwiązanie

Poniższa funkcja NajdalszaOdleglosc() używa przedstawionego wyżej algorytmu do obliczenia najdalszej odległości. Jako argumenty przyjmuje ile jest miejscowości oraz listę indeksów miejscowości, gdzie mieści się stacja.

  1. int NajdalszaOdleglosc(int n, vector<int> lista) {
  2.   sort(lista.begin(), lista.end());
  3.   int maksimum = lista[0];
  4.   for (int i = 1; i < lista.size(); i++) {
  5.     maksimum = max(abs(lista[i - 1] - lista[i]) / 2, maksimum);
  6.   }
  7.   maksimum = max(n - lista[lista.size() - 1] - 1, maksimum);
  8.   return maksimum;
  9. }

Początkowo maksymalna odległość wynosi tyle co odległość z miejscowości 0 do najbliższej tj. pierwszej stacji na trasie. Następnie pomiędzy każdymi kolejnymi stacjami jest obliczana odległość. Za każdym razem maksymalna odległość to maksimum z nowo obliczonej odległości oraz dotychczas znalezionej.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika potrzebne dane, a następnie wypisuje obliczoną maksymalną odległość.

  1. int main() {
  2.   int n, k, tmp;
  3.   cout << "Ile jest miast?\n n = ";
  4.   cin >> n;
  5.   cout << "Ile jest stacji?\n k = ";
  6.   cin >> k;
  7.   cout << "Podaj miasta ze stacjami:\n";
  8.   vector<int> lista;
  9.   while (k-- > 0) {
  10.     cin >> tmp;
  11.     lista.push_back(tmp);
  12.   }
  13.   cout << "Najdalsza odleglosc do stacji to ";
  14.   cout << NajdalszaOdleglosc(n, lista);
  15.   system("pause");
  16.   return 0;
  17. }