1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct mdata
  5 {
  6     int *pTime;
  7     int width;
  8     int hight;
  9     struct mdata *pre;
 10     struct mdata *next;
 11 }mhole;
 12 
 13 mhole *setHole(mhole *,int ,int ,int *);    //插入结点
 14 void pourTime(mhole *cur);                  //计算灌水时间
 15 void printTime(int *pTime,int N);           //输出灌水时间
 16 
 17 int main()
 18 {
 19     mhole *left,*right,*pt,*curHole;
 20     int N,mCount;
 21     int mWidth,mHight;
 22     int *time;
 23 
 24     left = (mhole*)malloc (sizeof(mhole));   //初始化左边界
 25     left->width = 0;
 26     left->hight = 1000000;
 27     left->pTime = NULL;
 28     left->pre = left->next = NULL;
 29 
 30 
 31     scanf("%d",&N);
 32     time = (int*)calloc(N,sizeof(mhole));    //time分配空间
 33 
 34     pt = curHole = left;                     //当前结点，坑底位置最低结点
 35     for(mCount = 0;mCount<N;mCount++){
 36         scanf("%d%d",&mWidth,&mHight);
 37         curHole = setHole(curHole,mWidth,mHight,time+mCount);
 38         if(pt->hight > mHight)                //坑底位置最低结点
 39             pt = curHole;
 40     }
 41     right = setHole(curHole,0,1000000,NULL);
 42 
 43     pourTime(pt);
 44     printTime(time,N);
 45 
 46     return 0;
 47 }
 48 mhole *setHole(mhole *preHole,int width,int hight,int *ptime)
 49 {
 50     mhole *curHole = (mhole *)malloc(sizeof(mhole));
 51     curHole->width = width;
 52     curHole->hight = hight;
 53     curHole->pTime = ptime;
 54     curHole->pre = preHole;
 55     curHole->next = NULL;
 56 
 57     preHole->next = curHole;
 58     return curHole;
 59 }
 60 void pourTime(mhole * curHole)
 61 {
 62     mhole *cur = curHole,*pt;
 63     int myclock = 0;
 64     while(cur->pre->hight != cur->next->hight){
 65         *(cur->pTime) = myclock + cur->width;
 66         //计算当前时间，合并以灌满结点
 67         if(cur->pre->hight > cur->next->hight){
 68             myclock += (cur->next->hight - cur->hight)*cur->width;
 69             cur->next->width += cur->width;
 70             //摘下pt，释放结点
 71             cur->pre->next = cur->next;
 72             cur->next->pre = cur->pre;
 73             pt = cur;
 74             cur = cur->next;
 75             free(pt);
 76         }
 77         else{
 78             myclock += (cur->pre->hight - cur->hight)*cur->width;
 79             cur->pre->width += cur->width;
 80 
 81             cur->pre->next = cur->next;
 82             cur->next->pre = cur->pre;
 83             pt = cur;
 84             cur = cur->pre;
 85             free(pt);
 86         }
 87         //移动至下一结点，此结点为当前坑底最低位置
 88         if(cur->hight < cur->pre->hight&&cur->hight < cur->next->hight)
 89             continue;
 90         else if(cur->pre->hight > cur->next->hight){     //右移
 91             while(cur->hight > cur->next->hight)
 92                 cur = cur->next;
 93             }else {
 94                 while(cur->hight >cur->pre->hight)
 95                     cur = cur->pre;
 96             }
 97     }
 98     myclock += cur->width;
 99     *(cur->pTime) = myclock;
100 }
101 void printTime(int *pTime,int N)
102 {
103     while(N--){
104         printf("%d\n",*pTime++);
105     }
106 }
107 
108 
109