Решение задачи 13.
Очевидным решением задачи является создание общего упорядоченного массива, содержащего элементы всех массивов, и нахождение в нем k-того по величине элемента. В этом случае требуется порядка (а1+а+...+an)*log(а1+а2+...+an) операций.
Однако можно существенно сократить трудоемкость, используя дихотомический способ поиска.
Пусть для каждого из наборов i определены начальный Ni и конечный Ki индексы. Определим индексы средних элементов Si=(Ni+Ki) div 2. Вычислим S=S1+S2+... +SN.
Возможны три ситуации:
1. S > k
Очевидно, что если найти минимальный элемент среди средних элементов (пусть он в наборе j), то ни один из элементов с индексами Sj,...,Kj заведомо не является решением. Поэтому можно пересчитать Kj=Sj-1 (если Kj>Nj).
2. S < k
Очевидно, что если найти максимальный элемент среди средних элементов (пусть он в наборе t), то ни один из элементов с индексами Nt,...,St заведомо не является решением. Поэтому можно пересчитать Nt=St+1 (если Kt>Nt).
3. S = k
Очевидно, что в этом случае можно пересчитать Kj=Sj и Nt=St+1.
Процесс заканчивается, когда начальный N[i] и конечный K[i] индексы удовлетворяют условию K[i]<=N[i] для каждого i. При этом меньший из элементов с индексами K[i] и будет искомым (если K[i]=0, то этот элемент рассматривать не нужно).
|
