Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //кластер
- #include <stdlib.h>
- #include <string.h>
- #include <stdio.h>
- struct Elem {
- int end_time;
- };
- typedef struct Elem Elem;
- int cmp(Elem a, Elem b) {
- return b.end_time - a.end_time;
- }
- struct PQ {
- Elem *heap;
- int cap;
- int count;
- };
- typedef struct PQ PQ;
- PQ *initPQ(int n) {
- PQ *q = malloc(sizeof(PQ));
- q->heap = malloc(sizeof(Elem) * n);
- q->cap = n;
- q->count = 0;
- return q;
- }
- void freePQ(PQ *q) {
- free(q->heap);
- free(q);
- }
- void addPQ(PQ *q, Elem n) {
- int i = q->count;
- if (q->count == q->cap)
- perror("overflow");
- q->count = i + 1;
- q->heap[i] = n;
- while (i > 0 && cmp(q->heap[(i - 1) / 2], q->heap[i]) < 0) {
- Elem tmp = q->heap[(i - 1) / 2];
- q->heap[(i - 1) / 2] = q->heap[i];
- q->heap[i] = tmp;
- i = (i - 1) / 2;
- }
- }
- void heapify(int i, int n, Elem *heap) {
- while (1) {
- int l = 2 * i;
- int r = l + 1;
- int j = i;
- if (l < n && cmp(heap[i], heap[l]) < 0)
- i = l;
- if (r < n && cmp(heap[i], heap[r]) < 0)
- i = r;
- if (i == j)
- break;
- Elem tmp = heap[i];
- heap[i] = heap[j];
- heap[j] = tmp;
- }
- }
- Elem popPQ(PQ *q) {
- if (q->count == 0)
- perror("empty");
- Elem p = q->heap[0];
- q->count--;
- if (q->count > 0) {
- q->heap[0] = q->heap[q->count];
- heapify(0, q->count, q->heap);
- }
- return p;
- }
- int emptyPQ(PQ *q) {
- return q->count == 0;
- }
- int main(int argc, char **argv) {
- int n;
- scanf("%d", &n);
- PQ *q = initPQ(n);
- int m;
- scanf("%d", &m);
- for(int i = 0; i < m; i++) {
- int start, duration;
- scanf("%d%d", &start, &duration);
- if(i < n) {
- addPQ(q, (Elem){start + duration});
- } else {
- Elem e = popPQ(q);
- if(e.end_time < start)
- addPQ(q, (Elem){start + duration});
- else
- addPQ(q, (Elem){e.end_time + duration});
- }
- }
- Elem last;
- while(!emptyPQ(q))
- last = popPQ(q);
- printf("%d", last.end_time);
- freePQ(q);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement