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!
More Questions From This User See All
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ă