Răspuns:
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int main() {
ifstream f("creioane.in");
//Citire date
int dim;
int* v;
f >> dim;
v = new int[dim];
for (int i = 0; i < dim; i++) {
f >> v[i];
}
f.close();
//Sortare rapida
sort(v, v + dim);
//Determinare creioare intre care exista diferenta minima
int primul_creion = 0;
for (int i = 1; i < dim - 1; i++) {
if (v[i + 1] - v[i] < v[primul_creion+1] - v[primul_creion]) {
primul_creion = i;
}
}
//Afisare creioane
ofstream g("creioane.out");
g << v[primul_creion+1] - v[primul_creion];
g.close();
}
Nota :
- Observam ca diferenta minima apar intre elemente consecutive atunci cand vectorul este sortat. Deci putem scrie programul mult mai eficient (complexitate [tex]O(nlogn)[/tex] - data de sortare) daca il sortam crescator.
- Abordarea naiva ar fi sa verificam distanta dintre fiecare pereche de numere [tex]v[i], v[j], \forall i=\overline{1,dim}, \forall j=\overline{i, dim}[/tex], care are o complexitate mai mare ( [tex]O(n^2)[/tex] ).
- Poti folosi orice sortare eficienta doresti (quicksort, mergesort, heapsort ai putea folosi chiar si count sort pentru o eficienta de O(n) stiind ca [tex]1 \leq v[i] \leq 1018[/tex]).
