Форум программистов [Powered by Invision Power Board]

Код

#include<stdio.h>
#include<stdlib.h>

typedef struct {
    int value;
    int  key;
} ITEM;

class HEAP {           //   создаем класс heap (двоичная куча)
public:
    ITEM *h;
    int  size;

    HEAP(unsigned int n) {
       size = 0;
       h = (ITEM*) malloc( sizeof(ITEM) * n);  //выделение памяти
    }

    ~HEAP() {
        if(h) free(h);
    }

    int add(ITEM x) {   //  добавляем новый элемент в конец кучи
       h[++size]=x;     //размер кучи +1 , т.к
                        // число шагов всплытия меньше чем высота дерева
       checkup(size);   // смотрим на родителя и проверяем свойство кучи
       return 1;
    }

    int extract_min(ITEM *x) {   // извлечение минимального элемента
      if(size ==0) return 0;     // если размер кучи равен 0 выход
      *x = h[1];                // отложим вершину кучи в сторону,
                                //чтобы в конце вернуть ее в качестве результата
      h[1] = h[size--];         // самый последний элемент в вершину кучи
      checkdown(1);             // "топим" его
      return 1;
    }
private:
    void checkup(int c) {          //    проверка сверху
        int p;                     // p-ключ родителя с-ключ ребенка
        p = c / 2;
        if( p == 0 )return;
                                   // сравниваем ключ ребенка с ключем родителя
        if(h[p].key > h[c].key) {  // если ключ родителя больше ключа ребенка
           ITEM tmp;
           tmp = h[p]; h[p] = h[c]; h[c] = tmp; //меняем их местами
           checkup(p);              // проверка сверху для нового родителя
        }
    }
    
    void checkdown(int p) {         //  проверка снизу
        int c;                      // p-ключ родителя с-ключ ребенка
        c = 2*p;
        if( c > size ) return;

        if( c+1 <= size && h[c + 1].key < h[c].key ) c++;
        if( h[c].key < h[p].key ) { // если ключ ребенка меньше ключа родителя
          ITEM tmp;
          tmp =  h[c]; h[c] = h[p]; h[p] = tmp; //меняем их местами
          checkdown(c);   // проверка снизу для нового ребенка
       }
    }
};

int main() {
    HEAP heap(1000);
    int n, i, k, j, z;
    ITEM x;

    scanf("%d", &n);                 // ввод количества колоколов
    scanf("%d", &k);                 // счет

    for(i = 0; i < n; i++){          // ввод элементов с приоритетами

       scanf("%d", &x.value);        // номер колокола
       scanf("%d", &x.key);          // его время
       heap.add(x);                  // добавляем элемент
    }
    for(i = 0; i < k; i++){
    while( heap.extract_min(&x) ) {  // извлекаем минимальный элемент
       j=x.value;                    // смотрим номер этого колокола
       x.value=x.value+x.key;        // прибавляем к приоритету этого элемента
       }                             // временной промежуток того колокола
    }
     printf("%d ", j);               // выводим результат
    return 0;
}