vadimk772336

Untitled

Oct 24th, 2021 (edited)
405
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdio>
  3. #include <vector>
  4. #include <list>
  5. using namespace std;
  6.  
  7.  
  8. //Реализовать кучу на массиве с операциями Add,Delete,SiftDown, удаление по указателю
  9. //Для списков аналогично удалаение по указателю и вставка перед элементом к которому обратились по указателю
  10. //Как получать адрес новго созданного отрезка? После создания или обяз после добавления в список?
  11.  
  12. // а<b
  13. bool operator<(const heap_element& a, const heap_element& b)
  14. {
  15.     int len_a = a.r-a.l;
  16.     int len_b = b.r-b.l;
  17.    
  18.     if ( (a.r-a.l < b.r-b.l) )
  19.         return true;
  20.     if ( (a.r-a.l == b.r-b.l) & (a.l > b.l))
  21.         return true;
  22.  
  23.     return false;
  24. }
  25.  
  26. struct heap_elements {
  27.     int l;
  28.     int r;
  29.     int position;
  30.     list_segments *to_list; //Указатель на себя в списке отрезков.
  31. };
  32.  
  33. struct list_segments {  //Структура отрезка - элемента списка отрезок
  34.     int l;
  35.     int r;
  36.     int status;         // Но лучше просто считать это элементов класса и делать del по указателю
  37.     int position; //Найдя по указателю отерзок поймём какой он в списке и вызовем del(pos)
  38.     struct list_segments *next;
  39.     struct list_segments *prev;
  40.     heap_elements *to_heap; //Указатель на себя в куче (элемент структуры heap_elements)
  41.    
  42. }
  43.  
  44. int main()
  45. {
  46.     //Массив указателей на отрезки (list_segments)
  47.     vector<*list_segments> requests;
  48.    
  49.     Heap heap;
  50.    
  51.     int N,M,K;
  52.  
  53.    
  54.     cin>> << N;
  55.     // Узнали N, можно добавить весь массив в структуры данных
  56.    
  57.     //Создание вершины и добавление в кучу
  58.     heap_elements vertex;
  59.     vertex.l = 1;
  60.     vertex.r = N;
  61.     vertex.to_list = NULL;
  62.     //adress = &vertex;  //?????????????
  63.     heap.add(vertex);
  64.  
  65.     //Cоздание списка отрезков
  66.     list_segments segment; //Создаем отрезок-структуру, заполняем
  67.     segment.l = 1;
  68.     segment.r = N;
  69.     segment.status = 1;
  70.     segment.position = 0; //Не надо, можно просто удалять
  71.     segment.next = NULL;
  72.     segment.prev = NULL;
  73.     segment.to_heap  = &heap[0]; //?????????????
  74.    
  75.     list <list_segments> segments; //Создаём пустой двусязный список
  76.     segments.push_back(segment);
  77.     vertex.to_list = &segments.back //Записываем в вершину запись её копии в списке отрезков (можно ли это сделать просто &segment?)
  78.    
  79.     cin >> M;
  80.     for (int i=0; i < M; ++i) { //Обрабатываем запросы
  81.    
  82.         cin >> K;
  83.        
  84.         if (K > 0) {
  85.             if (!heap.is_empty() & (heap[0].r-heap[0].l+1) >= K) {
  86.                
  87.                 //Меняем значение у структуры в вершине на [l+K,r]
  88.                 heap[0].l = l+K;
  89.                
  90.                 //о указателю из структуры в вершине находим отрезок [l,r] списка отрезков, меняем его на [l+K,r]
  91.                 heap[0].to_list->l = l+K;
  92.                
  93.                 //Создаём перед отрезком новый элемент списка [l,l+K−1], status=0, указатель пустой.
  94.                 //Написать класс  и просто делать init
  95.                 segment.l = l;
  96.                 segment.r = l+K-1;
  97.                 segment.status = 0;
  98.                 segment.position = heap.to_list->position - 1; //Не надо
  99.                 segments.to_heap = NULL;
  100.                 segments.push(segment, heap[0].to_list); //Перед  heap[0].to_list
  101.                
  102.                 //Делаем просеивание вершины    
  103.                 SiftDown(0);
  104.                
  105.                 //В массиве запросов на i−1 индексе записываем в указатель адрес созданного элемента списка.
  106.                 requests[i]  = &segments[segment.position];
  107.                
  108.                 cout << l;
  109.             }
  110.             else {
  111.                 requests[i] = NULL;
  112.                 cout << -1 << endl;
  113.             }
  114.         }
  115.        
  116.         else {
  117.             q = abs(K)-1;
  118.             if (requests[q] != NULL) {
  119.                 //Получаем по указателю из (q−1)-го элемента массива запросов адрес занятого отрезка в списке.
  120.                 //Меняем status с 0 на 1.
  121.                 requests[q]->status = 0;
  122.                
  123.                
  124.                 //Смотрим на отрезки слева и справа от освобожденного отрезка. Если отрезки идут подряд (один или оба),
  125.                 //то по указателям находим их в куче (один или оба) и удаляем, затем объединяем их в один.
  126.                 bool flag_l = false ,flag_r = false;
  127.                 if (requests[q]->prev->r == requests[q].l-1) {
  128.                     requests[q].l = requests[q]->prev->l //Слили с левым
  129.                    
  130.                     heap.del(requests[q]->prev->to_heap) // удаляем левый в куче
  131.                     segments.del(requests[q]->prev) // удаляем левый в списке отрезоков
  132.                 }
  133.                 if (requests[q]->next->l-1 == requests[q].r) {
  134.                     requests[q].r = requests[q]->next->r //Слили с правым
  135.                    
  136.                     heap.del(requests[q]->next->to_heap) // удаляем левый в куче
  137.                     segments.del(requests[q]->prev) // удаляем левый в списке отрезоков
  138.                 }
  139.  
  140.                 //Создаю новый элемент структуры для добавления в кучу.
  141.                 vertex = heap_elements(requests[q].l,requests[q].r,*requests[q])
  142.                
  143.                 //Указатель нового отрезка в списке приравниваю к адресу созданного элемента структуры.
  144.                 requests[q].to_heap = &vertex;
  145.                
  146.                 //Добавляю в кучу полученный отрезок с помощью Add.
  147.                 heap.Add(vertex);
  148.  
  149.             }
  150.            
  151.             else {
  152.                 requests[i] = NULL;
  153.             }
  154.         }
  155.        
  156.     }
  157.    
  158.    
  159.    
  160.  
  161.    
  162.    
  163.  
  164.        
  165.    
  166.  
  167.  
  168.     return 0;
  169. }
  170.  
  171.  
RAW Paste Data