vadimk772336

Untitled

Oct 27th, 2021
761
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.     if (h[HeapSize].to_list != NULL)
  100.         h[HeapSize].to_list->to_heap = HeapSize;
  101.     HeapSize++;
  102.     siftup();
  103.     /*
  104.   parent = (i-1)/2;
  105.   while(parent >= 0 && i > 0)  {
  106.     if(h[i] > h[parent]) {
  107.       int temp = h[i];
  108.       h[i] = h[parent];
  109.       h[parent] = temp;
  110.     }
  111.     i = parent;
  112.     parent = (i-1)/2;
  113.   }
  114.   */
  115. }
  116.  
  117. void Heap::siftdown(int position)
  118. {
  119.     int i, parent;
  120.     int max_child;
  121.     i = position;
  122.     int child1 = 2 * i + 1;
  123.     int child2 = 2 * i + 2;
  124.     if (h[child2] < h[child1])
  125.         max_child = child1;
  126.     else
  127.         max_child = child2;
  128.  
  129.     while (child1 < HeapSize)
  130.     {
  131.         if (child1 == HeapSize - 1)
  132.         {
  133.             max_child = child1;
  134.         }
  135.         else if (h[child2] < h[child1])
  136.             max_child = child1;
  137.         else
  138.             max_child = child2;
  139.  
  140.         if (h[i] < h[max_child])
  141.         {
  142.             heap_elements temp = h[i];
  143.             h[i] = h[max_child];
  144.             h[max_child] = temp;
  145.             h[i].position = i;
  146.             h[max_child].position = max_child;
  147.             h[i].to_list->to_heap = i;
  148.             h[max_child].to_list->to_heap = max_child;
  149.         }
  150.         i = max_child;
  151.         child1 = 2 * i + 1;
  152.         child2 = 2 * i + 2;
  153.     }
  154. }
  155.  
  156. void Heap::delete_vertex(int position)
  157. {
  158.  
  159.     h[position] = h[HeapSize - 1];
  160.     h[HeapSize - 1].l = 0;
  161.     h[HeapSize - 1].r = 0;
  162.     HeapSize--;
  163.     siftdown(position);
  164. }
  165.  
  166. void Heap::out(void)
  167. {
  168.     for (int i = 0; i < HeapSize; i++)
  169.     {
  170.         cout << h[i].l << " " << h[i].r << " ";
  171.     }
  172.     cout << endl;
  173. }
  174.  
  175.  
  176. // LIST SEGMENT BEGIN -----------------------------------------
  177. class LIST_SEGMENTS
  178. {
  179.     struct list_segments *Head, *Tail;
  180.     struct list_segments* element;
  181.     int Count;
  182.  
  183. public:
  184.     LIST_SEGMENTS(); // конструктор кучи
  185.     // LIST_SEGMENTS(int, int, int, struct list_segments*, struct list_segments*,int); //
  186.     // конструктор кучи
  187.     void add(int, int, int, list_segments*, int);
  188.     void delete_segment(list_segments*);
  189.     void Print();
  190.     void add_head(int, int, int, int);
  191.     list_segments* get_head();
  192.     // void out(); // вывод элементов кучи в форме массива
  193. };
  194.  
  195. LIST_SEGMENTS::LIST_SEGMENTS()
  196. {
  197.     // Изначально список пуст
  198.     Head = Tail = NULL;
  199.     Count = 0;
  200. }
  201. void LIST_SEGMENTS::add_head(int l, int r, int status, int to_heap)
  202. {
  203.     // новый элемент
  204.     list_segments* temp = new list_segments;
  205.  
  206.     // Предыдущего нет
  207.     temp->prev = 0;
  208.     // Заполняем данные
  209.     temp->l = l;
  210.     temp->r = r;
  211.     temp->status = status;
  212.     // Следующий - бывшая голова
  213.     temp->next = Head;
  214.  
  215.     // Если элементы есть?
  216.     if (Head != 0)
  217.         Head->prev = temp;
  218.  
  219.     // Если элемент первый, то он одновременно и голова и хвост
  220.     if (Count == 0)
  221.         Head = Tail = temp;
  222.     else
  223.         // иначе новый элемент - головной
  224.         Head = temp;
  225.  
  226.     Count++;
  227. }
  228.  
  229. /*
  230. LIST_SEGMENTS::LIST_SEGMENTS(struct list_segments* segment,int l, int r, int status, struct
  231. list_segments* next, struct list_segments* prev,
  232.     int to_heap)
  233. {
  234.     segment = new list_segments;
  235.     segment.l = l;
  236.     segment.r = r;
  237.     segment.status = status;
  238.     segment.next = next;
  239.     segment.prev = prev;
  240.     segment.to_heap = to_heap;
  241. }
  242. */
  243.  
  244. void LIST_SEGMENTS::add(int l, int r, int status, list_segments* segment, int to_heap)
  245. {
  246.     // struct list_segments* next;
  247.     // struct list_segments* prev;
  248.     // prev = segment;
  249.     //*next = &(segment->next);
  250.     list_segments* segment2 = new list_segments;
  251.     // LIST_SEGMENTS(elem,l, r, status, &(segment->next), &segment, to_heap);
  252.     segment2->l = l;
  253.     segment2->r = r;
  254.     segment2->status = status;
  255.     segment2->next = segment->next;
  256.     segment2->prev = segment;
  257.     segment2->to_heap = to_heap;
  258.     if (segment->next != NULL)
  259.         segment->next->prev = segment2;
  260.     segment->next = segment2;
  261.     Count++;
  262. }
  263. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  264. {
  265.     if (segment->next != NULL)
  266.         segment->next->prev = segment->prev;
  267.     if (segment->prev != NULL)
  268.         segment->prev->next = segment->next;
  269.     else
  270.         Head = segment->next;
  271.     delete segment; // или free или любое другое удаление хзхзхз
  272. }
  273. void LIST_SEGMENTS::Print()
  274. {
  275.     // Если в списке присутствуют элементы, то пробегаем по нему
  276.     // и печатаем элементы, начиная с головного
  277.     list_segments* temp = Head;
  278.     cout << "( ";
  279.     while (temp->next != NULL)
  280.     {
  281.         cout << temp->l << ", " << temp->r << ";";
  282.         temp = temp->next;
  283.     }
  284.  
  285.     cout << temp->l << "," << temp->r << " )\n";
  286. }
  287. list_segments* LIST_SEGMENTS::get_head()
  288. {
  289.     return Head;
  290. }
  291.  
  292. // LIST SEGMENT END
  293.  
  294. int main()
  295. {
  296.  
  297.     //-------------------------------------------------------- REAL ЗАГАТОВКА
  298.     //Массив указателей на отрезки (list_segments)
  299.  
  300.  
  301.     Heap heap;
  302.  
  303.     int N, M, K;
  304.  
  305.     //cout << "Enter N: " ;
  306.     cin >> N;
  307.     //N = 6;
  308.    
  309.     // Узнали N, можно добавить весь массив в структуры данных
  310.  
  311.     //Создание вершины и добавление в кучу
  312.    
  313.     heap_elements vertex;
  314.     vertex.l = 1;
  315.     vertex.r = 6;
  316.     vertex.to_list = NULL;
  317.     vertex.position = 0;
  318.     cout << "1" << endl;
  319.    
  320.     LIST_SEGMENTS List; //Создаём пустой двусязный список
  321.     List.add_head(1, N, 1, 0);
  322.    
  323.    
  324.     vertex.to_list = List.get_head();
  325.     heap.add(vertex);
  326.     cout << "1" << endl;
  327.     // Cоздание списка отрезков
  328.     list_segments segment; //Создаем отрезок-структуру, заполняем
  329.  
  330.  
  331.  
  332.      //Записываем в вершину запись её копии в списке отрезков
  333.     //(можно ли это сделать просто &segment?)
  334.  
  335.  
  336.     heap_elements* heap_head;
  337.     //cout << "Enter M: " ;
  338.     cin >> M;
  339.     //M = 3;
  340.     list_segments* requests[M];
  341.     for (int i = 0; i < M; ++i)
  342.     { //Обрабатываем запросы
  343.         //cout << "Запрос номер " << i << endl;
  344.         //cout << "\n Enter K: \n" ;
  345.         cin >> K;
  346.  
  347.         if (K > 0)
  348.         {
  349.            
  350.             heap_head = heap.get_head();
  351.             if ((heap_head->r - heap_head->l + 1) >= K)
  352.             {
  353.                 if ((heap_head->r - heap_head->l + 1) == K){
  354.                     heap_head->to_list->status=0;
  355.                     requests[i] = heap_head->to_list;
  356.                     cout << "answer: " << heap_head->l << endl;
  357.                     heap.delete_vertex(0);
  358.                 }
  359.                 else{
  360.                     cout << "Можем откусить \n" << endl;
  361.                     //Меняем значение у структуры в вершине на [l+K,r]
  362.                     int old_l = heap_head->l;
  363.                     heap_head->l = old_l + K;
  364.                     cout << "Изменившаяся куча после откусывания: " <<heap_head->l<< "\n";
  365.                    
  366.                     //о указателю из структуры в вершине находим отрезок [l,r] списка отрезков, меняем
  367.                     //его на [l+K,r]
  368.                     //cout << "1" << endl;
  369.                     heap_head->to_list->l = old_l + K;
  370.                     //cout << "2" << endl;
  371.                     //Создаём перед отрезком новый элемент списка [l,l+K−1], status=0, указатель пустой.
  372.                     //Написать класс  и просто делать init
  373.                     segment.l = old_l;
  374.                     segment.r = old_l + K - 1;
  375.                     segment.status = 0;
  376.                     segment.to_heap = -1;
  377.                     //cout << "3" << endl;
  378.                     if (heap_head->to_list->prev != NULL)
  379.                     {
  380.                         List.add(old_l, old_l + K - 1, 0, heap_head->to_list->prev, -1);
  381.                         requests[i] = heap_head->to_list->prev;
  382.                     }
  383.                     else
  384.                     {
  385.                         List.add_head(old_l, old_l + K - 1, 0, -1);
  386.                         requests[i] = List.get_head();
  387.                     }
  388.    
  389.    
  390.                     //Делаем просеивание вершины
  391.                     heap.siftdown(0);
  392.    
  393.                     cout << "answer: " << old_l << endl;
  394.                 }
  395.             }
  396.             else
  397.             {
  398.                 requests[i] = NULL;
  399.                 cout << "answer:" << -1 << endl;
  400.             }
  401.         }
  402.  
  403.         else
  404.         {
  405.             int q = abs(K) -1;
  406.             if (requests[q] != NULL)
  407.             {
  408.                 //Получаем по указателю из (q−1)-го элемента массива запросов адрес занятого отрезка
  409.                 //в списке.
  410.                 //Меняем status с 0 на 1.
  411.                 requests[q]->status = 1;
  412.  
  413.                 //Смотрим на отрезки слева и справа от освобожденного отрезка. Если отрезки идут
  414.                 //подряд (один или оба),
  415.                 //то по указателям находим их в куче (один или оба) и удаляем, затем объединяем их в
  416.                 //один.
  417.                 if (requests[q]->prev != NULL){
  418.                     if (requests[q]->prev->status == 1 & requests[q]->prev->r == requests[q]->l - 1)
  419.                     {
  420.                         requests[q]->l = requests[q]->prev->l; //Слили с левым
  421.                         heap.delete_vertex(requests[q]->prev->to_heap); // удаляем левый в куче
  422.                         List.delete_segment(requests[q]->prev); // удаляем левый в списке отрезоков
  423.                     }
  424.                 }
  425.                 if (requests[q]->next != NULL){
  426.                     if (requests[q]->next->status == 1 &  requests[q]->next->l - 1 == requests[q]->r)
  427.                     {
  428.                         requests[q]->r = requests[q]->next->r; //Слили с правым
  429.    
  430.                         heap.delete_vertex(requests[q]->next->to_heap); // удаляем левый в куче
  431.                         List.delete_segment(requests[q]->next); // удаляем левый в списке отрезоков
  432.                     }
  433.                 }
  434.  
  435.                 //Создаю новый элемент структуры для добавления в кучу.
  436.                 //vertex = heap_elements(requests[q].l, requests[q].r, *requests[q]);
  437.                     vertex.l = requests[q]->l;
  438.                     vertex.r = requests[q]->r;
  439.                     vertex.to_list = requests[q];
  440.                     vertex.position = 0;  //заполнится само
  441.                     heap.add(vertex);
  442.                
  443.                
  444.                 //Указатель нового отрезка в списке приравниваю к адресу созданного
  445.                 //элемента структуры.
  446.                 //requests[q].to_heap = &vertex; Сделается автоматически кучей в Add и Siftup
  447.  
  448.             }
  449.  
  450.             else
  451.             {
  452.                 requests[i] = NULL;
  453.             }
  454.         }
  455.     heap.out();
  456.     List.Print();
  457.     cout << "------ \n";
  458.     }
  459.  
  460.     return 0;
  461. }
  462.  
RAW Paste Data