Question

Se dă un vector cu n elemente, numere naturale și un număr k. Ordonați crescător primele k elemente ale vectorului și descrescător ultimele n-k elemente. Pentru sortare se va folosit metoda QuickSort sau MergeSort. Date de intrare Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului. Date de ieșire Programul va afișa pe ecran elementele vectorului, separate prin exact un spațiu, după efectuarea operațiilor cerute. Restricții și precizări 1 ≤ k < n ≤ 200 000 cele n numere citite vor fi mai mici decât 1 000 000 000

Answer 1

#include <iostream>
#define maxN 200005
using namespace std;
int n,k,v[maxN],w1[maxN],x;
void mergesort(int st, int dr)
{
    if(st < dr)
    {
        int m=(st+dr)/2;
        mergesort(st,m);
        mergesort(m+1,dr);
        int i=st,j=m+1,k=0;
        while(i<=m && j<=dr)
        {
            if(v[i]<v[j]) w1[++k]=v[i++];
            else w1[++k]=v[j++];
        }
        while(i<=m)
            w1[++k]=v[i++];
        while(j<=dr)
            w1[++k]=v[j++];
        j=1;
        for(i=st;i<=dr;i++)
            v[i]=w1[j],j++;
    }
}
int main()
{
    cin>>n>>k;
    for(int x=1;x<=n;x++)
        cin>>v[x];
    mergesort(1,k);
    for(x=1;x<=k;x++) cout<<v[x]<<" ";
    mergesort(k+1,n);
    for(x=n;x>k;x--) cout<<v[x]<<" ";
    return 0;
}