Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Program dostaje od użytkownika liczby (każda inna) ma wyświetlić parę bądź pary liczb o najmniejszej różnicy
- Wejście
- program na początku w pierwszej linii otrzymuje liczbę n<=1000000.
- następnie w liniach otrzymuje n RÓŻNYCH liczb z zakresu od 0 do 1000000.
- Wyjście
- Program ma na początku wyświetlić wartość bezwzględną najmniejszej różnicy pomiędzy liczbami. Następnie program ma wyświetlić parę (bądź pary, w przypadku, gdy jest ich więcej) liczb o najmniejszej różnicy. Przez różnicę rozumiemy różnicę liczby większej od liczby mniejszej (różnica będzie zawsze dodatnia). Pary mają być wyświetlone od najmniejszych do największych. W parze także wyświetlamy najpierw liczbę mniejsza potem liczbę większą.
- Przykład
- Wejście
- 5
- 4
- 7
- 1
- 9
- 13
- Wyjście
- 2
- 7 9
- Przykład 2
- Wejście
- 8
- 4
- 7
- 1
- 9
- 13
- 11
- 75
- 21
- Wyjście
- 2
- 7 9
- 9 11
- 11 13
- UWAGA: Program powinien działać w złożoności O(nlog(n)).
- UWAGA: Zabronione jest używanie wbudowanych algorytmów sortujących
- #include <iostream>
- using namespace std;
- int lSyn(int i)
- {
- return (2*i+1);
- }
- int pSyn(int i)
- {
- return (2*i+2);
- }
- void heapFix(int *tab, int i, int heapsize)
- {
- int largest=i,pom;
- int lewySyn=lSyn(i);
- int prawySyn=pSyn(i);
- if(lewySyn<heapsize && tab[i]<tab[lewySyn])
- largest=lewySyn;
- if(prawySyn<heapsize && tab[prawySyn]>tab[largest])
- largest=prawySyn;
- if(i!=largest){
- pom=tab[i];
- tab[i]=tab[largest];
- tab[largest]=pom;
- heapFix(tab,largest,heapsize);
- }
- }
- void buildHeap(int *tab, int n)
- {
- for(int i=n/2;i>=0;i--)
- {
- heapFix(tab,i,n);
- }
- }
- void heapSort(int *tab,int dl)
- {
- buildHeap(tab,dl);
- int heapsize = dl;
- while(heapsize>0)
- {
- heapsize--;
- int pom = tab[0];
- tab[0]=tab[heapsize];
- tab[heapsize]=pom;
- heapFix(tab,0,heapsize);
- }
- }
- int find(int *tab, int rozmiar)
- {
- int save;
- int najmniejsza = 1000001;
- for(int i=0; i<rozmiar-1; i++)
- {
- save = tab[i+1]-tab[i];
- if (save < najmniejsza){
- najmniejsza=save;
- }
- }
- return najmniejsza;
- }
- void wyswietl(int *tab, int rozmiar)
- { int najmniejsza = find(tab,rozmiar);
- cout<<najmniejsza<<endl;
- for(int i=0; i<rozmiar-1; i++)
- if( (tab[i+1] - tab[i]) == najmniejsza )
- cout<<tab[i]<<" "<<tab[i+1]<<endl;
- }
- int main(){
- int rozmiar;
- cin>>rozmiar;
- int *tab=new int[rozmiar];
- for(int i=0; i<rozmiar; i++)
- cin>>tab[i];
- heapSort
- (tab, rozmiar);
- wyswietl(tab, rozmiar);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement