Horce-racing Duals

 

Tikslas

Kasablankos hipodrome yra organizuojamos naujo tipo žirgų lenktynės: poromis. Tai reiškia, kad vienu metu varžosi tik du žirgai. Kad lenktynės būtų įdomesnės, būtina parinkti kuo panašesnės jėgos žirgus. 

Parašykite programą, kuri rastų du žirgus kuo mažesniu jegos skirtumu ir parodykite jų jėgos skirtumą teigiamu skaičiumi.

 

Sprendimas

Surašykite visus žirgus į masyvą, nes duomenys yra nuo 2 iki 100000 žirgų. Dabar belieka sutikrinti žirgus vienus su kitais ir rasti mažiausią skirtumą. Kadangi yra laiko limitai ir esant labai dideliam žirgų kiekiui, programai neužtenka laiko patikrinti visus variantus. Reikai ieškoti kito būdo. Galima žirgus surikiuoti didėjimo tvarka ir tikrinti tik gretimus.

 

Patarimai

Masyvo kūrimas int A[N]

Masyvo rikiavimas sort(A, A+N). Norint naudoti sort, reikia papildomos bibliotekos #include <algorithm>

 

Pseudo kodas

Horse