Advertisement
Guest User

Untitled

a guest
Oct 21st, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. Program dostaje od użytkownika liczby (każda inna) ma wyświetlić parę bądź pary liczb o najmniejszej różnicy
  2.  
  3. Wejście
  4.  
  5. program na początku w pierwszej linii otrzymuje liczbę n<=1000000.
  6. następnie w liniach otrzymuje n RÓŻNYCH liczb z zakresu od 0 do 1000000.
  7. Wyjście
  8.  
  9. 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ą.
  10. Przykład
  11.  
  12. Wejście
  13.  
  14. 5
  15. 4
  16. 7
  17. 1
  18. 9
  19. 13
  20. Wyjście
  21.  
  22. 2
  23. 7 9
  24. Przykład 2
  25.  
  26. Wejście
  27.  
  28. 8
  29. 4
  30. 7
  31. 1
  32. 9
  33. 13
  34. 11
  35. 75
  36. 21
  37. Wyjście
  38.  
  39. 2
  40. 7 9
  41. 9 11
  42. 11 13
  43. UWAGA: Program powinien działać w złożoności O(nlog(n)).
  44.  
  45. UWAGA: Zabronione jest używanie wbudowanych algorytmów sortujących
  46.  
  47.  
  48. #include <iostream>
  49.  
  50. using namespace std;
  51.  
  52. int lSyn(int i)
  53. {
  54.     return (2*i+1);
  55.  
  56. }
  57.  
  58. int pSyn(int i)
  59. {
  60.     return (2*i+2);
  61.  
  62. }
  63.  
  64.  
  65. void heapFix(int *tab, int i, int heapsize)
  66. {
  67.  
  68. int largest=i,pom;
  69. int lewySyn=lSyn(i);
  70. int prawySyn=pSyn(i);
  71.  
  72. if(lewySyn<heapsize && tab[i]<tab[lewySyn])
  73.     largest=lewySyn;
  74.  
  75.  
  76. if(prawySyn<heapsize && tab[prawySyn]>tab[largest])
  77.     largest=prawySyn;
  78.  
  79. if(i!=largest){
  80.     pom=tab[i];
  81.     tab[i]=tab[largest];
  82.     tab[largest]=pom;
  83.     heapFix(tab,largest,heapsize);
  84. }
  85.  
  86.  
  87. }
  88.  
  89. void buildHeap(int *tab, int n)
  90. {
  91.     for(int i=n/2;i>=0;i--)
  92.     {
  93.         heapFix(tab,i,n);
  94.     }
  95. }
  96.  
  97. void heapSort(int *tab,int dl)
  98. {
  99.     buildHeap(tab,dl);
  100.         int heapsize = dl;
  101.  
  102.     while(heapsize>0)
  103.     {
  104.         heapsize--;
  105.         int pom = tab[0];
  106.         tab[0]=tab[heapsize];
  107.         tab[heapsize]=pom;
  108.         heapFix(tab,0,heapsize);
  109.  
  110.     }
  111. }
  112.  
  113. int find(int *tab, int rozmiar)
  114. {
  115.     int save;
  116.     int najmniejsza = 1000001;
  117.    for(int i=0; i<rozmiar-1; i++)
  118.    {
  119.  
  120.    save = tab[i+1]-tab[i];
  121.     if (save < najmniejsza){
  122.      najmniejsza=save;
  123.     }
  124.    }
  125.    return najmniejsza;
  126.  
  127. }
  128.  
  129.  void wyswietl(int *tab, int rozmiar)
  130. {     int najmniejsza = find(tab,rozmiar);
  131.         cout<<najmniejsza<<endl;
  132.         for(int i=0; i<rozmiar-1; i++)
  133.             if( (tab[i+1] - tab[i]) == najmniejsza )
  134.                 cout<<tab[i]<<" "<<tab[i+1]<<endl;
  135.  }
  136.  
  137. int main(){
  138.  
  139.   int rozmiar;
  140.   cin>>rozmiar;
  141.  
  142.   int *tab=new int[rozmiar];
  143.  
  144.   for(int i=0; i<rozmiar; i++)
  145.     cin>>tab[i];
  146.  
  147.   heapSort
  148.   (tab, rozmiar);
  149.   wyswietl(tab, rozmiar);
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement