Даны два отсортированных по неубыванию массива A и B, состоящих из целых чисел. Проверьте, можно ли в массиве Aвыбрать k чисел, а в массиве B — выбрать m чисел так, что любое число, выбранное в первом массиве, строго меньше любого числа, выбранного во втором массиве.
В первой строке заданы два целых числа nA, nB (1 ≤ nA, nB ≤ 105), разделенные пробелом — размеры массивов A и B, соответственно.
Во второй строке записаны два челых числа k и m (1 ≤ k ≤ nA, 1 ≤ m ≤ nB), разделенные пробелом.
В третьей строке записаны nA чисел a1, a2, … anA ( - 109 ≤ a1 ≤ a2 ≤ … ≤ anA ≤ 109), разделенных пробелами — элементы массива A.
В четвертой строке записаны nB чисел b1, b2, … bnB ( - 109 ≤ b1 ≤ b2 ≤ … ≤ bnB ≤ 109), разделенных пробелами — элементы массива B.
Выведите «YES» (без кавычек), если в массиве A можно выбрать k чисел, а в массиве B — m чисел так, любое выбранное в массиве A число строго меньше любого выбранного в массиве B числа. В противном случае выведите «NO» (без кавычек).
|
1 2 3 4 |
3 3 2 1 1 2 3 3 4 5 |
|
1 |
YES |
|
1 2 3 4 |
3 3 3 3 1 2 3 3 4 5 |
|
1 |
NO |
|
1 2 3 4 |
5 2 3 1 1 1 1 1 1 2 2 |
|
1 |
YES |
В первом тестовом примере, можно например, выбрать числа 1 и 2 из массива A и число 3 из массива B (1 < 3 и 2 < 3).
Во втором тестовом примере единственный способ выбрать k элементов в первом массиве и m элементов во втором — выбрать все числа в обоих массивах, но тогда не все выбранные числа в A будут меньше, чем все выбранные в B: 
.
Моё решение:
Сперва слегка смутило «по неубыванию», но потом включилась алгебра логики и выражение легко превратилось в «по возрастанию». Ошибкой было то, что я опять позабыл про то, что JavaScript не обязательно переведет строку в число перед сравнением. Только утром на дорешивании исправил свою оплошность. Теперь всякий раз, когда нужно будет получить числа, а не строки то просто на всякий случай ввод переведу явно из строк в числа.
Само решение простое. сравниваем k самых маленьких чисел первого массива с самыми большими m числами второго массива. Учитывая, что оба массивы уже отсортированными к нам приходят, то проблем вообще ни каких нет.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//считываем входные данные: var data = readline().split(' '); var Na = parseInt(data[0]); var MasA=[]; var MasB=[]; var Nb = parseInt(data[1]); var data = readline().split(' '); var k = parseInt(data[0]); var m = parseInt(data[1]); var data = readline().split(' '); for (i=0;i<Na;i++){ MasA[i]=parseInt(data[i]); } var data = readline().split(' '); for (i=0;i<Nb;i++){ MasB[i]=parseInt(data[i]); } //собственно само решение задачи: var result = "YES" if (MasA[k-1]>=MasB[MasB.length-m]){ result = "NO"; } //выводим резкльтат write(result); |