Перевод кода на С++.

[opax]

Задача:

Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ...аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

Решение:

(То, что не могу понять как реализовать - выделено курсивом)

Пусть числа 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; {переходим к следующим элементам}
[I]если v[k]=(a[i],a[j])
то пусть количество оставшихся в массиве A элементов справа
от а[i-1], равных a[i-1], есть u, т.е. a=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;
конец_если
конец_если
конец_пока

#include <cstdlib> 
#include <iostream>

using namespace std;


void qs(int *items, int left, int right)//быстрая сортировка - по неубыванию
{
  register int i, j;
  char x, y;
 
  i = left; j = right;
  x = items[(left+right)/2];
 
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
 
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
 
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}
void quick(int *items, int count)
{
  qs(items, 0, count-1);
}


int main(int argc, char *argv[])

{   int a[500],n,l,i,j,u,v,k;
    pair <int,int> vec[500];
    cout<<"Vvedite kolichestvo elementov posledovatel'nosti:"<<endl;
    cin>>n;
    
    cout<<"Vvedite elementi posledovatel'nosti:"<<endl;
    for (l=0;l<n;l++){
        cin>>a[l];} //вводим последовательность
        cout<<endl;
        quick(a,n); //сортируем по неубыванию

        k=0; 
        i=0;
        j=n-1;
        
        while (i<j){
        k=k+1;
        vec[k].first=a[i],
        vec[k].second=a[j];
        i++;j--; 
        
        
        
        
        if (u>=v)
        (j=j-v-1);
        else
        (i=i+u+1);
        

        cout<<vec[k].first<<"  "<<vec[k].second<<endl;}
        
             

    system("PAUSE");
    return EXIT_SUCCESS;
}