Question

Luați o secvență de 2n numere reale ca intrare. Realizați un algoritm O(n log n) care împarte numerele în n perechi, cu proprietatea
că partiția minimizează suma maximă a unei perechi.

De exemplu, spunem noi, sunt numerele (1,6,3,7), partițiile posibile sunt
( (1,6), (3,7) ), ( (1,3), (6,7) ) și ( (1,7), (3,6) ).
Sumele pereche pentru aceste partiții sunt (4,13), (7,10) și (8,9). Astfel, a treia partiție are 9 ca suma maximă, adică
minimul pe cele trei partiții.

Rezolvarea sa fie în C sau C++. (As dori în special in C, dar merge si in C++).
Vă rog!

Answer 1

Răspuns:

#include <iostream>

#include <algorithm>

using namespace std;

int n,i,v[200],smin;

int main()

{

   cout << "n= "; cin >> n;

   cout << "introdu " << 2*n << " numere naturale " << endl;

   for (i=0; i<2*n; ++i)

       cin >> v[i];

   sort(v,v+n);

   smin=v[n-1]+v[n];

   cout << smin;

   return 0;

}

Explicație:

făcând o cercetare (câteva exemple pe hârtie :))) ) am ajuns la concluzia că perechia căutată este cea din mijlocul şirului ordonat

dacă şirul este 1 6 3 7, după ordonare obţinem 1 3 6 7 şi deci perechia (3,6) este cea căutată