vadimk772336

Untitled

Oct 27th, 2021
925
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. using namespace std;
  5.  
  6. struct heap_elements;
  7.  
  8. struct list_segments
  9. { //Структура отрезка - элемента списка отрезок
  10.  
  11.     int l;
  12.     int r;
  13.     int status; // Но лучше просто считать это элементов класса и делать del по указателю
  14.     struct list_segments* next;
  15.     struct list_segments* prev;
  16.     int to_heap; //Указатель на себя в куче (элемент структуры heap_elements)
  17. };
  18.  
  19. struct heap_elements
  20. {
  21.     int l;
  22.     int r;
  23.     int position;
  24.     list_segments* to_list; //Указатель на себя в списке отрезков.
  25. };
  26.  
  27.  
  28. bool operator<(const heap_elements& a, const heap_elements& b)
  29. {
  30.     int len_a = a.r - a.l;
  31.     int len_b = b.r - b.l;
  32.  
  33.     if ((a.r - a.l < b.r - b.l))
  34.         return true;
  35.     if ((a.r - a.l == b.r - b.l) & (a.l > b.l))
  36.         return true;
  37.  
  38.     return false;
  39. }
  40.  
  41.  
  42. class Heap
  43. {
  44.     static const int SIZE = 100; // максимальный размер кучи
  45.     struct heap_elements* h; // указатель на массив кучи
  46.     int HeapSize; // размер кучи
  47. public:
  48.     Heap(); // конструктор кучи
  49.     void add(heap_elements); // добавление элемента кучи
  50.     void outHeap(); // вывод элементов кучи в форме кучи
  51.     void out(); // вывод элементов кучи в форме массива
  52.     void siftup();
  53.     void siftdown(int);
  54.     void delete_vertex(int);
  55.     heap_elements get_head();
  56. };
  57.  
  58. Heap::Heap()
  59. {
  60.     h = new heap_elements[SIZE];
  61.     HeapSize = 0;
  62. }
  63.  
  64. heap_elements Heap::get_head()
  65. {
  66.     return h[0];
  67. }
  68.  
  69.  
  70. void Heap::siftup()
  71. {
  72.     int i, parent;
  73.     i = HeapSize - 1;
  74.     parent = (i - 1) / 2;
  75.     while (parent >= 0 && i > 0)
  76.     {
  77.         if (h[parent] < h[i])
  78.         {
  79.             heap_elements temp = h[i];
  80.             h[i] = h[parent];
  81.             h[parent] = temp;
  82.             h[i].position = i;
  83.             h[parent].position = parent;
  84.             h[i].to_list->to_heap = i;
  85.             h[parent].to_list->to_heap = parent;
  86.         }
  87.         i = parent;
  88.         parent = (i - 1) / 2;
  89.     }
  90. }
  91.  
  92. void Heap::add(heap_elements elem)
  93. {
  94.  
  95.     h[HeapSize] = elem;
  96.     // h[HeapSize].r = elem.r;
  97.     // h[HeapSize].to_list=elem.to_list;
  98.     h[HeapSize].position = HeapSize;
  99.     h[HeapSize].to_list->to_heap = HeapSize;
  100.     HeapSize++;
  101.     siftup();
  102.     /*
  103.   parent = (i-1)/2;
  104.   while(parent >= 0 && i > 0)  {
  105.     if(h[i] > h[parent]) {
  106.       int temp = h[i];
  107.       h[i] = h[parent];
  108.       h[parent] = temp;
  109.     }
  110.     i = parent;
  111.     parent = (i-1)/2;
  112.   }
  113.   */
  114. }
  115.  
  116. void Heap::siftdown(int position)
  117. {
  118.     int i, parent;
  119.     int max_child;
  120.     i = position;
  121.     int child1 = 2 * i + 1;
  122.     int child2 = 2 * i + 2;
  123.     if (h[child2] < h[child1])
  124.         max_child = child1;
  125.     else
  126.         max_child = child2;
  127.  
  128.     while (child1 < HeapSize)
  129.     {
  130.         if (child1 == HeapSize - 1)
  131.         {
  132.             max_child = child1;
  133.         }
  134.         else if (h[child2] < h[child1])
  135.             max_child = child1;
  136.         else
  137.             max_child = child2;
  138.  
  139.         if (h[i] < h[max_child])
  140.         {
  141.             heap_elements temp = h[i];
  142.             h[i] = h[max_child];
  143.             h[max_child] = temp;
  144.             h[i].position = i;
  145.             h[max_child].position = max_child;
  146.             h[i].to_list->to_heap = i;
  147.             h[max_child].to_list->to_heap = max_child;
  148.         }
  149.         i = max_child;
  150.         child1 = 2 * i + 1;
  151.         child2 = 2 * i + 2;
  152.     }
  153. }
  154.  
  155. void Heap::delete_vertex(int position)
  156. {
  157.  
  158.     h[position] = h[HeapSize - 1];
  159.     h[HeapSize - 1].l = 0;
  160.     h[HeapSize - 1].r = 0;
  161.     HeapSize--;
  162.     siftdown(position);
  163. }
  164.  
  165. void Heap::out(void)
  166. {
  167.     for (int i = 0; i < HeapSize; i++)
  168.     {
  169.         cout << h[i].l << " " << h[i].r << " ";
  170.     }
  171.     cout << endl;
  172. }
  173.  
  174.  
  175. // LIST SEGMENT BEGIN -----------------------------------------
  176. class LIST_SEGMENTS
  177. {
  178.     struct list_segments *Head, *Tail;
  179.     struct list_segments* element;
  180.     int Count;
  181.  
  182. public:
  183.     LIST_SEGMENTS(); // конструктор кучи
  184.     // LIST_SEGMENTS(int, int, int, struct list_segments*, struct list_segments*,int); //
  185.     // конструктор кучи
  186.     void add(int, int, int, list_segments*, int);
  187.     void delete_segment(list_segments*);
  188.     void Print();
  189.     void add_head(int, int, int, int);
  190.     list_segments* get_head();
  191.     // void out(); // вывод элементов кучи в форме массива
  192. };
  193.  
  194. LIST_SEGMENTS::LIST_SEGMENTS()
  195. {
  196.     // Изначально список пуст
  197.     Head = Tail = NULL;
  198.     Count = 0;
  199. }
  200. void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
  201. {
  202.     // новый элемент
  203.     list_segments* temp = new list_segments;
  204.  
  205.     // Предыдущего нет
  206.     temp->prev = 0;
  207.     // Заполняем данные
  208.     temp->l = l;
  209.     temp->r = r;
  210.     temp->status = status;
  211.     // Следующий - бывшая голова
  212.     temp->next = Head;
  213.  
  214.     // Если элементы есть?
  215.     if (Head != 0)
  216.         Head->prev = temp;
  217.  
  218.     // Если элемент первый, то он одновременно и голова и хвост
  219.     if (Count == 0)
  220.         Head = Tail = temp;
  221.     else
  222.         // иначе новый элемент - головной
  223.         Head = temp;
  224.  
  225.     Count++;
  226. }
  227.  
  228. /*
  229. LIST_SEGMENTS::LIST_SEGMENTS(struct list_segments* segment,int l, int r, int status, struct
  230. list_segments* next, struct list_segments* prev,
  231.     int to_heap)
  232. {
  233.     segment = new list_segments;
  234.     segment.l = l;
  235.     segment.r = r;
  236.     segment.status = status;
  237.     segment.next = next;
  238.     segment.prev = prev;
  239.     segment.to_heap = to_heap;
  240. }
  241. */
  242.  
  243. void LIST_SEGMENTS::add(int l, int r, int status, list_segments* segment, int to_heap)
  244. {
  245.     // struct list_segments* next;
  246.     // struct list_segments* prev;
  247.     // prev = segment;
  248.     //*next = &(segment->next);
  249.     list_segments* segment2 = new list_segments;
  250.     // LIST_SEGMENTS(elem,l, r, status, &(segment->next), &segment, to_heap);
  251.     segment2->l = l;
  252.     segment2->r = r;
  253.     segment2->status = status;
  254.     segment2->next = segment->next;
  255.     segment2->prev = segment;
  256.     segment2->to_heap = to_heap;
  257.     if (segment->next != NULL)
  258.         segment->next->prev = segment2;
  259.     segment->next = segment2;
  260.     Count++;
  261. }
  262. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  263. {
  264.     if (segment->next != NULL)
  265.         segment->next->prev = segment->prev;
  266.     if (segment->prev != NULL)
  267.         segment->prev->next = segment->next;
  268.     else
  269.         Head = segment->next;
  270.     delete segment; // или free или любое другое удаление хзхзхз
  271. }
  272. void LIST_SEGMENTS::Print()
  273. {
  274.     // Если в списке присутствуют элементы, то пробегаем по нему
  275.     // и печатаем элементы, начиная с головного
  276.     list_segments* temp = Head;
  277.     cout << "( ";
  278.     while (temp->next != NULL)
  279.     {
  280.         cout << temp->l << ", " << temp->r << ";";
  281.         temp = temp->next;
  282.     }
  283.  
  284.     cout << temp->l << "," << temp->r << " )\n";
  285. }
  286. list_segments* LIST_SEGMENTS::get_head()
  287. {
  288.     return Head;
  289. }
  290.  
  291. // LIST SEGMENT END
  292.  
  293. int main()
  294. {
  295.  
  296.     //-------------------------------------------------------- REAL ЗАГАТОВКА
  297.     //Массив указателей на отрезки (list_segments)
  298.  
  299.  
  300.     Heap heap;
  301.  
  302.     int N, M, K;
  303.  
  304.     cout << "Enter N: " ;
  305.     cin >> N;
  306.    
  307.    
  308.     // Узнали N, можно добавить весь массив в структуры данных
  309.  
  310.     //Создание вершины и добавление в кучу
  311.     heap_elements vertex;
  312.     vertex.l = 1;
  313.     vertex.r = N;
  314.     vertex.to_list = NULL;
  315.     vertex.position = 0;
  316.     cout << "1" << endl;
  317.     heap.add(vertex);
  318.     cout << "1" << endl;
  319.     // Cоздание списка отрезков
  320.     list_segments segment; //Создаем отрезок-структуру, заполняем
  321.     segment.l = 1;
  322.     segment.r = N;
  323.     segment.status = 1;
  324.     // segment.position = 0; //Не надо, можно просто удалять
  325.     segment.next = NULL;
  326.     segment.prev = NULL;
  327.     segment.to_heap = 0; //?????????????
  328.  
  329.     LIST_SEGMENTS List; //Создаём пустой двусязный список
  330.     List.add_head(1, N, 1, 0);
  331.     vertex.to_list = List.get_head(); //Записываем в вершину запись её копии в списке отрезков
  332.     //(можно ли это сделать просто &segment?)
  333.  
  334.  
  335.     heap_elements heap_head;
  336.     cout << "Enter M: " ;
  337.     cin >> M;
  338.     list_segments* requests[M];
  339.     for (int i = 0; i < M; ++i)
  340.     { //Обрабатываем запросы
  341.  
  342.         cout << "Enter K: " ;
  343.         cin >> K;
  344.  
  345.         if (K > 0)
  346.         {
  347.            
  348.             heap_head = heap.get_head();
  349.             if ((heap_head.r - heap_head.l + 1) >= K)
  350.             {
  351.  
  352.                 //Меняем значение у структуры в вершине на [l+K,r]
  353.                 int old_l = heap_head.l;
  354.                 heap_head.l = old_l + K;
  355.  
  356.                 //о указателю из структуры в вершине находим отрезок [l,r] списка отрезков, меняем
  357.                 //его на [l+K,r]
  358.                 heap_head.to_list->l = old_l + K;
  359.  
  360.                 //Создаём перед отрезком новый элемент списка [l,l+K−1], status=0, указатель пустой.
  361.                 //Написать класс  и просто делать init
  362.                 segment.l = old_l;
  363.                 segment.r = old_l + K - 1;
  364.                 segment.status = 0;
  365.                 segment.to_heap = -1;
  366.  
  367.                 if (heap_head.to_list->prev != NULL)
  368.                 {
  369.                     List.add(old_l, old_l + K - 1, 0, heap_head.to_list->prev, -1);
  370.                     requests[i] = heap_head.to_list->prev;
  371.                 }
  372.                 else
  373.                     List.add_head(old_l, old_l + K - 1, 0, -1);
  374.                 requests[i] = List.get_head();
  375.  
  376.  
  377.                 //Делаем просеивание вершины
  378.                 heap.siftdown(0);
  379.  
  380.                 cout << old_l;
  381.             }
  382.             else
  383.             {
  384.                 requests[i] = NULL;
  385.                 cout << -1 << endl;
  386.             }
  387.         }
  388.  
  389.         else
  390.         {
  391.             int q = abs(K) - 1;
  392.             if (requests[q] != NULL)
  393.             {
  394.                 //Получаем по указателю из (q−1)-го элемента массива запросов адрес занятого отрезка
  395.                 //в списке.
  396.                 //Меняем status с 0 на 1.
  397.                 requests[q]->status = 1;
  398.  
  399.  
  400.                 //Смотрим на отрезки слева и справа от освобожденного отрезка. Если отрезки идут
  401.                 //подряд (один или оба),
  402.                 //то по указателям находим их в куче (один или оба) и удаляем, затем объединяем их в
  403.                 //один.
  404.  
  405.                 if (requests[q]->prev != NULL & requests[q]->prev->r == requests[q]->l - 1)
  406.                 {
  407.                     requests[q]->l = requests[q]->prev->l; //Слили с левым
  408.                     heap.delete_vertex(requests[q]->prev->to_heap); // удаляем левый в куче
  409.                     List.delete_segment(requests[q]->prev); // удаляем левый в списке отрезоков
  410.                 }
  411.                 if (requests[q]->next != NULL & requests[q]->next->l - 1 == requests[q]->r)
  412.                 {
  413.                     requests[q]->r = requests[q]->next->r; //Слили с правым
  414.  
  415.                     heap.delete_vertex(requests[q]->next->to_heap); // удаляем левый в куче
  416.                     List.delete_segment(requests[q]->next); // удаляем левый в списке отрезоков
  417.                 }
  418.  
  419.                 //Создаю новый элемент структуры для добавления в кучу.
  420.                 //vertex = heap_elements(requests[q].l, requests[q].r, *requests[q]);
  421.                     vertex.l = requests[q]->l;
  422.                     vertex.r = requests[q]->r;
  423.                     vertex.to_list = requests[q];
  424.                     vertex.position = 0;  //заполнится само
  425.                     heap.add(vertex);
  426.                
  427.                
  428.                 //Указатель нового отрезка в списке приравниваю к адресу созданного
  429.                 //элемента структуры.
  430.                 //requests[q].to_heap = &vertex; Сделается автоматически кучей в Add и Siftup
  431.  
  432.             }
  433.  
  434.             else
  435.             {
  436.                 requests[i] = NULL;
  437.             }
  438.         }
  439.        
  440.     cout << "Запрос ------ " << M << "\n";
  441.     heap.out();
  442.     List.Print();
  443.     cout << "------ \n";
  444.     }
  445.  
  446.     return 0;
  447. }
  448.  
RAW Paste Data