Задача 20.
Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ...аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.
|
Решение задачи 20.
Пусть числа a[1], ..., a[n] расположены в порядке неубывания (если это не так, то просто отсортируем массив). Будем выписывать искомые векторы v[1], ..., следующим образом:
Пусть k - номер формируемого сейчас вектора.
Положим сначала индекс i первого элемента формируемого сейчас вектора v[k] равным 1, а индекс второго элемента j=N.
k:=0;
пока (i<j) повторять {пока есть возможные элементы для пар}
k:=k+1;
v[k]:=(a[i],a[j]);
полагаем i:=i+1; j:=j-1; {переходим к следующим элементам}
если v[k]=(a[i],a[j])
то пусть количество оставшихся в массиве A элементов справа
от а[i-1], равных a[i-1], есть u, т.е. a[i]=a[i+1]=...=a[i+u],
а количество оставшихся в массиве A элементов слева от а[j+1], равных a[j+1], есть v, т.е.
a[j]=a[j-1]=...=a[j-v].
если u>=v
то, так как мы стремимся получить максимальное число пар,
то мы отбросим все оставшиеся элементы со значением a[j] и положим j:=j-v-1
иначе по аналогичной причине отбросим все оставшиеся элементы со значением a[i], т.е. положим i:=i+u+1;
конец_если
конец_если
конец_пока
|
