Advertisement
Guest User

Untitled

a guest
Feb 21st, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef unsigned long int ulint;
  5.  
  6. struct kraj{
  7. int p;
  8. ulint w;
  9. };
  10.  
  11. int main(){
  12. ios_base::sync_with_stdio(false);
  13. int n,i,k,p,max;
  14. ulint m,j,w,ile=0;
  15. kraj *K; //tablica - kopiec
  16. cin>>n;
  17. int panstwa[1001];
  18. K = new kraj[n];
  19. // kraj kr;
  20. int pom, pom2;
  21. for(i=0;i<n;i++)
  22. {
  23. cin >> p >> w;
  24. //cin>>K[i].p >> K[i].w;
  25. K[i].p = p;
  26. K[i].w = w;
  27. panstwa[p]=i;
  28. }
  29. cin>>m;
  30. for(j=0;j<m;j++)
  31. {
  32. cin>>p>>w;
  33. // i=0;
  34. i = panstwa[p];
  35. // while(K[i].p != p) //znajduje indeks odpowiedniego panstwa..
  36. // i++;
  37. K[i].w = w; //.. i nadaje mu nowy wspolczynnik
  38. //TAB[SZUKANY] 'k'=OJCIEC
  39.  
  40.  
  41. if((i>0)&&(w > K[k = (i-1)/2].w))
  42. { //jezeli K[i] jest wiekszy od ojca (o ile MA ojca)
  43. while((i>0)&&(w>K[k].w))
  44. { //przesuwa K[i] w gore odpowiednia ilosc razy
  45. //k=(i-1)/2; // indeks ojca
  46. //zamienia miejscami K[i] z K[k]:
  47. //tab[ojciec].wsp pom=K[k].p;
  48. //tab[szukany].wsp pom2=K[i].p;
  49. swap(panstwa[pom2],panstwa[pom] );
  50. swap(K[i],K[k]);
  51.  
  52. ile++;
  53. i = k; k = (i-1)/2;
  54.  
  55. }
  56. }
  57. else
  58. {
  59. k=2*i+1;
  60. if(((k<n)&&(w<K[k].w)) || ((k+1<n)&&(w<K[k+1].w)))
  61. { //.. a jezeli K[i] MA lewego/prawego syna - i jest od ktoregos mniejszy..
  62. /*k=lsyn*/ while(((k<n)&&(w<K[k].w)) || ((k+1<n)&&(w<K[k+1].w)))
  63. { //przesuwa K[i] w dol
  64. if((k+1<n)&&(K[k+1].w>K[k].w)) //okresla wiekszego z synow
  65. max = k+1; //prawy jest wiekszy
  66. else
  67. max = k; //lewy jest wiekszy //max to index wiekszego z synow elementu K[i]
  68. //zamienia miejscami K[i] z K[max]:
  69. pom=K[max].p;
  70. pom2=K[i].p;
  71. swap(panstwa[pom2],panstwa[pom] );
  72. swap(K[i],K[max]);
  73. ile++;
  74. i=max; k=2*i+1;
  75.  
  76. }
  77. }
  78. }
  79. }
  80.  
  81. cout<<ile;
  82. return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement