Question

Cătălin are N creioane, fiecare creion i având lungimea a[i]. El trebuie sa aleagă 2 creioane ca să scrie tema la mate. Ca un matematician adevărat, lui Cătălin îi place simetria: el vrea să aleagă cele două creioane astfel încât ele să fie cât mai asemănătoare (să aibă diferența dintre lungimi minimă). Rolul vostru este să îi ziceți lui Cătălin care este aceasta diferență minimă.
Date de intrare
În fișierul creioane.in se află pe prima linie numărul N iar pe a doua line N numere.
Date de ieșire
Afișați în fișierul creioane.out diferența minimă dintre oricare două elemente.
Restricții și precizări
2 ≤ N ≤ 100000
1 ≤ a[i] ≤ 1018

Answer 1

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 $O(nlogn)$ - data de sortare) daca il sortam crescator.

• Abordarea naiva ar fi sa verificam distanta dintre fiecare pereche de numere $v[i], v[j], \forall i=\overline{1,dim}, \forall j=\overline{i, dim}$, care are o complexitate mai mare ( $O(n^2)$ ).

• Poti folosi orice sortare eficienta doresti (quicksort, mergesort, heapsort ai putea folosi chiar si count sort pentru o eficienta de O(n) stiind ca $1 \leq v[i] \leq 1018$).