include stdio include stdlib struct claster int end struct Pqueue int

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <stdlib.h>
struct claster
{
int end;
};
struct Pqueue
{
int cap,count;
struct claster *h;
};
void InitPqueue(struct Pqueue* pq, int ClastCount)
{
pq->h = (struct claster*)malloc(ClastCount * sizeof(struct claster));
pq->cap = ClastCount;
pq->count = 0;
}
void insert(struct Pqueue *pq,int ptr)
{
int i;
i=pq->count;
pq->count=i+1;
pq->h[i].end=ptr;
struct claster Swap;
while(i>0 && pq->h[(i-1)/2].end > pq->h[i].end)
{
Swap=pq->h[(i-1)/2];
pq->h[(i-1)/2]=pq->h[i];
pq->h[i]=Swap;
i = (i-1)/2;
}
}
void insert1(struct Pqueue *pq,int ptr)
{
int i;
i=pq->count-1;
pq->h[i].end=ptr;
struct claster Swap;
while(i>0 && pq->h[(i-1)/2].end > pq->h[i].end)
{
Swap=pq->h[(i-1)/2];
pq->h[(i-1)/2]=pq->h[i];
pq->h[i]=Swap;
i = (i-1)/2;
}
}
void Heapify(struct Pqueue* pq)
{
int l, r, j,i;
struct claster swap;
for(i = 0;;)
{
l = 2*i+1;
r = l+1;
j = i;
if(l < pq->count && pq->h[l].end < pq->h[j].end)
{
j = l;
}
if(r < pq->count && pq->h[r].end < pq->h[j].end)
{
j = r;
}
if(i == j)
{
break;
}
swap = pq->h[i];
pq->h[i] = pq->h[j];
pq->h[j] = swap;
i = j;
}
}
int main (int argc, char const *argv[])
{
int ClastCount,i,NumOfOperations=0,swap=0;
scanf("%d", &ClastCount );
scanf("%d", &NumOfOperations );
struct Pqueue pq;
InitPqueue(&pq, ClastCount);
int time[NumOfOperations][2];
for(i = 0; i < ClastCount; i++)
{
scanf("%d", &time[i][0] );
scanf("%d", &time[i][1] );
time[i][1]+=time[i][0];
insert(&pq,time[i][1]);
}
Heapify(&pq);
for (; i<NumOfOperations; i++)
{
scanf("%d", &time[i][0] );
scanf("%d", &time[i][1] );
time[i][1]+=time[i][0];
if (pq.h[0].end < time[i][0])
{
pq.h[0].end=time[i][1];
}
else
{
pq.h[0].end+=time[i][1]-time[i][0];
}
swap=pq.h[0].end;
pq.h[0].end=pq.h[pq.cap-1].end;
insert1(&pq,swap);
Heapify(&pq);
}
for (i=0;i<ClastCount;i++)
{
if (swap<pq.h[i].end)
{
swap=pq.h[i].end;
}
}
printf("%d",swap);
free(pq.h);
return 0;
}