Массив

[vadiprog]

Целочисленный массив X из n элементов разбит на m фрагментов. В целочисленном массиве K из m элементов хранятся длины соответствующих фрагментов (все K[i] различны, их сумма равна n). Упорядочить массив K по возрастанию, переставив соотвествующие фрагменты в массиве X.

[vadiprog]

к примеру есть массив X[10]=1,2,3,4,5,6,7,8,9,10. разделили его на 4 неравные части. 1ый фрагмент: 1,2,3. 2ой: 4. 3ий: 5,6,7,8. 4ий: 9,10. и массив получился к[4]= 3,1,4,2. потом сортируем массив х, чтобы массив к стал упорядочным. тогда будет х[10]=4,9,10,1,2,3,5,6,7,8 и к[4]=1,2,3,4.

Вот как должно работать, помогите программу написать

[Abstraction]

Надеюсь, второй массив завести можно?
Первое, что нам понадобится - карта массива K. Это такой массив S, что i-ый его элемент содержит индекс i-го по возрастанию элемента K. Например (индексы от 0):

K = {3, 1, 4, 2}    K = {4, 9, 6, 1, 3}
S = {1, 3, 0, 2}    S = {3, 4, 0, 2, 1}

Как его получить? Ну, например, скопировать массив K в массив K`, завести массив S, инициализировав его упорядоченной последовательностью {0, 1, 2, ..., m-1} (индексы от 0), а потом упорядочить K`, но всякий раз, когда в массиве K` будут меняться местами два элемента, одновременно менять элементы с теми же индексами в массиве S. Проверьте сами, что способ работает (он аналогичен тому, как в линейной алгебре получают обратную матрицу, приписывая к исходной сбоку единичную).

Ну, а дальше мы заводим массив X` и последовательно, для каждого элемента S определяемся, какому фрагменту в X он соответствует и дописываем этот фрагмент в X`. В примере,
S[0]=1, сумма K[i<1] равна 3, K[1]+3=4, в X` добавляются X[3<=i<4];
S[1]=3, сумма K[i<3] равна 8, K[3]+8=10, в X` добавляются X[8<=i<10];
S[2]=0, сумма K[i<0] равна 0, K[0]+0=3, в X` добавляются X[0<=i<3];
S[3]=2, сумма K[i<2] равна 4, K[2]+4=8, в X` добавляются X[4<=i<8];