Pagini recente » Cod sursa (job #72442) | Cod sursa (job #1501512) | Cod sursa (job #2585067) | Cod sursa (job #1014493) | Cod sursa (job #435035)
Cod sursa(job #435035)
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#define true 1
#define false 0
#define MinData -MAXINT
typedef struct gutuie {
int w;
int h;
} Gutuie;
typedef struct Node{
Gutuie g;
struct Node *next;
unsigned char noOfElements;
} node;
typedef node* linkedList;
typedef struct heapStruct {
int Capacity;
int Size;
Gutuie *Gutui;
} HeapStruct;
typedef HeapStruct* PriorityQueue;
void merge(Gutuie * v, int s, int m, int d) {
int i = s;
int j = m + 1;
int k = 0;
Gutuie v2[100000];
while (i <= m && j <= d) {
if (v[i].w < v[j].w) {
v2[k++] = v[i++];
}
else {
v2[k++] = v[j++];
}
}
for (; i <= m ; i++){
v2[k++] = v[i];
}
for (;j <= d ; j++){
v2[k++] = v[j];
}
for (i = 0 ; i <= (d-s) ; i++){
v[i+s] = v2[i];
}
}
void mSort(Gutuie * v, int s, int d) {
if (s < d) {
int m = (s+d)/2;
mSort(v,s,m);
mSort(v,m+1,d);
merge(v,s,m,d);
}
}
PriorityQueue MakeQueue(int MaxCapacity) {
PriorityQueue Q = (PriorityQueue)malloc(sizeof(HeapStruct));
Q -> Capacity = MaxCapacity;
Q -> Size = 0;
Q -> Gutui = (Gutuie*)malloc(MaxCapacity*sizeof(Gutuie));
Q -> Gutui[0].w = MinData;
Q -> Gutui[0].h = MinData;
return Q;
}
/* Q -> Gutuie[0] este santinela */
void Insert(Gutuie oGutuie, PriorityQueue Q) {
int i;
for (i = ++ Q -> Size ; Q -> Gutui[i / 2].w > oGutuie.w ; i /= 2)
Q -> Gutui [i] = Q -> Gutui [i / 2];
Q -> Gutui [i] = oGutuie;
}
Gutuie DeleteMin(PriorityQueue Q) {
int i, Child;
Gutuie MinElement, LastElement;
MinElement = Q -> Gutui[1];
LastElement = Q -> Gutui[Q -> Size --];
for (i = 1; i * 2 <= Q->Size; i = Child) {
Child = i * 2;
if (Child != Q -> Size && Q -> Gutui[Child + 1].w < Q -> Gutui[Child].w)
Child++;
if (LastElement.w > Q -> Gutui[Child].w)
Q -> Gutui[i] = Q -> Gutui[Child];
else break;
}
Q -> Gutui [i] = LastElement;
return MinElement;
}
int IsEmpty(PriorityQueue Q) {
if (Q -> Size == 0)
return 1;
return 0;
}
node* newNode (Gutuie oGutuie, node *nextNode){
node *aNode = (node*)malloc(sizeof(node));
aNode -> g = oGutuie;
aNode -> next = nextNode;
aNode -> noOfElements = 0;
return aNode;
}
void setNext(node *aNode, node* nextNode){
aNode -> next = nextNode;
}
void listInsertDesc(linkedList aList, int maxEl, node *aNode) {
node * tempNode = aList;
setNext(aNode,tempNode->next);
setNext(tempNode,aNode);
}
int isEmpty(linkedList aList){
if (aList -> next == NULL)
return true;
return false;
}
Gutuie getNextNode(linkedList aList){
node * tempNode = aList -> next;
aList -> next = aList -> next -> next;
return tempNode -> g;
}
void printList(linkedList aList) {
node * tempNode = aList -> next;
while (tempNode != NULL){
printf("%d %d\n",tempNode -> g.h, tempNode -> g.w);
tempNode = tempNode ->next;
}
}
int main() {
FILE *fin, *fout;
int N, H, U;
fin = fopen("gutui.in","r");
fout = fopen("gutui.out","w");
fscanf(fin,"%d %d %d", &N, &H, &U);
int i;
Gutuie *v = (Gutuie*)malloc(N*sizeof(Gutuie));
// Read elements
for (i = 0 ; i < N ; i++) {
fscanf(fin,"%d %d", &v[i].h, &v[i].w);
}
// Sort elements
mSort(v,0,N-1);
// Make list of lists
int noOfLists = H/U;
if (H % U) noOfLists++;
linkedList *lists = (linkedList*) malloc (noOfLists * sizeof(linkedList));
for (i = 0 ; i < noOfLists ; i++) {
lists[i] = (linkedList) malloc(sizeof(node));
lists[i] -> noOfElements = 0;
}
// Fill the lists
for (i = 0 ; i < N ; i++) {
int listNo;
listNo = (H - v[i].h)/U;
listInsertDesc(lists[listNo],N,newNode(v[i],NULL));
}
free(v);
PriorityQueue Q = MakeQueue(H / U + 1);
for (i = 0 ; i < noOfLists ; i++) {
while (isEmpty(lists[i]) == false) {
Gutuie oGutuie = getNextNode(lists[i]);
if (Q -> Size == (i + 1) && Q -> Gutui[1].w > oGutuie.w)
break;
else Insert(oGutuie, Q);
if (Q -> Size > i + 1)
DeleteMin(Q);
}
}
unsigned long long suma = 0;
while (IsEmpty(Q) == 0) {
Gutuie x = DeleteMin(Q);
suma += x.w;
}
fprintf(fout,"%lld\n",suma);
fclose(fin);
fclose(fout);
return 0;
}