[C++][Algorytmy] Wojsko Napoleona - V OIG

[alu675]

Witam. Chciałbym, żeby ktoś wyjaśnił mi zadanie "Wojsko Napoleona" z V OIG:

Wojsko szykuje się na wizytację Napoleona. Oczywiście wszyscy chcieliby wypaść jak najlepiej. Żołnierze muszą podzielić się na oddziały, które kolejno będzie oglądać cesarz. Wszyscy zdają sobie sprawę, ze ma on obsesję na punkcie wzrostu, więc chcieliby, żeby grupy były pod tym względem tak wyrównane, jak tylko się da. W tym celu wyprawiają niestworzone rzeczy. Zakładają wysokie czapki, buty na wysokim obcasie, udają garbatych... Każdy żołnierz może tak wyglądać, jakby miał dowolny wzrost z określonego dla niego przedziału. Pomóż wojsku ustawić się tak, aby największa różnica wzrostu wewnątrz grupy była jak najmniejsza.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby \(\displaystyle{ N}\) i \(\displaystyle{ M}\) (\(\displaystyle{ 1 \le M \le N \le 10^{6}}\)), oznaczające liczbę żołnierzy i liczbę oddziałów, na które muszą się podzielić. W kolejnych \(\displaystyle{ N}\) wierszach znajdują się po dwie liczby \(\displaystyle{ A_{i}}\) i \(\displaystyle{ B_{i}}\) (\(\displaystyle{ 1 \le A_{i} \le B_{i} \le 10^{9}}\)), oznaczające, że żołnierz \(\displaystyle{ i}\) może wyglądać na wzrost pomiędzy \(\displaystyle{ A_{i}}\) i \(\displaystyle{ B_{i}}\) włącznie.

Wyjście

W pierwszym wierszu standardowego wyjścia powinna znaleźć się jedna liczba, oznaczająca minimalną możliwa największą różnicę wzrostu wewnątrz oddziału.

Przykłady

Wejście:
6 2
1 3
2 4
3 5
4 6
5 7
6 8

Wyjście:
0


Wejście:
8 2
1 2
2 2
3 4
3 3
5 6
4 6
6 8
7 9

Wyjście:
1


Wejście:
7 2
4 10
18 20
4 11
2 3
10 13
1 5
19 20

Wyjście:
6

[Mistrz]

Wyjaśnić, czyli nie rozumiesz treści? Zobacz: w pierwszym wejściu masz podane, że jest 6 żołnierzy (o zakresach 1-3, 2-4, 3-5, 4-6, 5-7, 6-8), którzy mają się podzielić na 2 oddziały. Odpowiedź to 0, bo jeżeli do jednego oddziału damy pierwszych trzech (1-3, 2-4, 3-5), a do drugiego pozostałych (4-6, 5-7, 6-8) to wówczas Ci pierwsi mogą sobie ustawić wzrost wszyscy na 3, a w drugim oddziale na 6. Wtedy różnica między każdymi dwoma z jednego oddziału będzie 0.

[alu675]

Nie. Chodzi mi o to, w jaki sposób rozwiązać to zadanie. Nie mam żadnego pomysłu...-- 23 kwi 2012, o 19:47 --Nikt nie pomoże?

[cyberciq]

alu675, skąd wziąłeś to zadanie? jest gdzieś do tego sprawdzarka w ogóle? Bo ja nie mogę znaleźć tego na liście z V OIG. Jak masz linka to zapodaj.

pozdrawiam