Cipele
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 90\) points
After spending most of his money on various projects, Nadan decided to afford high quality shoes for
his software developers. Luckily for Nadan, he found \(N\) left shoes and \(M\) right shoes in his basement.
Since their origin is unknown, the shoes come in various sizes.
Nadan asked you to pair as many shoes as possible (it’s important that a new pair cannot be
selected after pairing all the shoes). Each pair should consist of one left shoe and one right shoe.
While pairing the shoes, you should make sure that the ugliness is minimized. The ugliness of one
pairing is defined as the maximal absolute difference of the shoe sizes between all pairs of shoes.
In test cases worth 20% of total points, it will hold that \(N\) = \(M\) .
In test cases worth additional 50% of total points, it will hold that \(N\) , \(M\) ≤ 5 000.
The first line contains two positive integers \(N\) and M (1 ≤ \(N\) , \(M \le 100\,000\)), the number of left shoes
and right shoes, in that order.
The second line contains \(N\) numbers \(L\) {i}{ } (1 ≤ \(L\) {i}{ } ≤ 10 {9}{ }), the sizes of the left shoes.
The third line contains \(M\) numbers \(R\) {i}{ } (1 ≤ \(R\) {i}{ } ≤ 10 {9}{ }), the sizes of the right shoes.
Output the minimal ugliness between all possible shoe pairings.
2 3
2 3
1 2 3
4 3
2 39 41 45
39 42 46
5 5
7 6 1 2 10
9 11 6 3 12output
output
0
1
4Clarification of the second sample test:
Nadan has 4 left and 3 right shoes, maximal number of pairs that can be obtained is 3. One possible pairing is:
39 - 46 , 41 - 42, 45 - 39, but ugliness of such pairing is 7 because of the first pair.
Better pairing would be:
39 - 39, 41 - 42, 45 - 46, with ugliness being equal to 1, which is minimal possible ugliness that can be
obtained.
평가 및 의견
Cipele
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cipele