Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. //WORKS!!!
  5.  
  6. using std::cin;
  7. using std::cout;
  8. using std::vector;
  9. using std::endl;
  10. using std::swap;
  11.  
  12. struct Customer {
  13. int start_time;
  14. int end_time;
  15. int ads_showed;
  16.  
  17. Customer();
  18. Customer(int beg, int end);
  19. };
  20.  
  21. Customer::Customer() { }
  22. Customer::Customer(int beg, int end) {
  23. start_time = beg;
  24. end_time = end;
  25. ads_showed = 0;
  26. }
  27.  
  28. //сравнение
  29.  
  30.  
  31. bool isBigger(Customer L, Customer R) {
  32. if (L.end_time > R.end_time) {
  33. return true;
  34. } else if (L.end_time == R.end_time) {
  35. return L.start_time > R.start_time;
  36. } else {
  37. return false;
  38. }
  39. }
  40.  
  41.  
  42. //HEAP
  43.  
  44. class Heap {
  45.  
  46. public:
  47. Heap();
  48. ~Heap();
  49.  
  50. void push(Customer val);
  51. void adUpdater(unsigned long start_index, unsigned long adTime); //обновить элементы кучи при добавлении нового показа рекламы
  52. void siftDown(unsigned long index, unsigned long heap_size);
  53. void heapSort();
  54. void buildHeap();
  55. unsigned getMinAdsCount(); //получить минимальное кол-во рекламы
  56.  
  57. private:
  58. vector<Customer> buffer;
  59. };
  60.  
  61. Heap::Heap() { }
  62.  
  63. Heap::~Heap() {
  64. buffer.empty();
  65. }
  66.  
  67. void Heap::push(Customer val){
  68. buffer.push_back(val);
  69. }
  70.  
  71. void Heap::buildHeap()
  72. {
  73. for (long i = buffer.size() / 2 - 1; i >= 0; --i) {
  74. siftDown(buffer.size(), i);
  75. }
  76. }
  77.  
  78. void Heap::siftDown(unsigned long heapSize, unsigned long i )
  79. {
  80. unsigned long left = 2 * i + 1;
  81. unsigned long right, largest;
  82.  
  83. while (left < heapSize) {
  84. right = left + 1;
  85. largest = i;
  86.  
  87. if(isBigger(buffer[left], buffer[i])) {
  88. largest = left;
  89. }
  90. if(right < heapSize && isBigger(buffer[right], buffer[largest])) {
  91. largest = right;
  92. }
  93.  
  94. if( largest != i ) {
  95. swap(buffer[i], buffer[largest]);
  96. i = largest;
  97. left = 2 * i + 1;
  98. } else {
  99. return;
  100. }
  101. }
  102. }
  103.  
  104. void Heap::heapSort() {
  105. for (unsigned long i = buffer.size() - 1; i > 0; --i) {
  106. swap(buffer[0], buffer[i]);
  107. siftDown(i, 0);
  108. }
  109.  
  110. }
  111.  
  112. void Heap::adUpdater(unsigned long start_index, unsigned long adTime) {
  113. for (unsigned long i = start_index; i < buffer.size(); ++i) {
  114. if(buffer[i].start_time <= adTime && buffer[i].end_time >= adTime) {
  115. ++(buffer[i].ads_showed);
  116. }
  117. }
  118. }
  119.  
  120. unsigned Heap::getMinAdsCount() {
  121. unsigned ads = 0;
  122. for (int i = 0; i < buffer.size(); ++i){
  123. if (buffer[i].ads_showed == 0) {
  124. adUpdater(i, buffer[i].end_time - 1);
  125. ++ads;
  126. }
  127. if (buffer[i].ads_showed == 1) {
  128. adUpdater(i, buffer[i].end_time);
  129. ++ads;
  130. }
  131. }
  132. return ads;
  133. }
  134.  
  135.  
  136. // MAIN
  137.  
  138. int main() {
  139. unsigned n;
  140. cin >> n;
  141. Heap heap;
  142. for(unsigned i = 0; i < n; ++i) {
  143. int start, end;
  144. cin >> start >> end;
  145. heap.push(Customer(start, end));
  146. }
  147.  
  148. heap.buildHeap();
  149. heap.heapSort();
  150.  
  151. cout << heap.getMinAdsCount();
  152.  
  153. return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement