vadimk772336

Untitled

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