堆，不解释。题意在讨论里面有。
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 struct HEAP 7 { 8 int p,id,px; 9 }h[10010],tmp; 10 int t,size; 11 inline bool cmp(const HEAP &a,const HEAP &b) 12 { 13 if(a.px==b.px) return a.id>b.id; 14 else return a.px>b.px; 15 } 16 void read() 17 { 18 while(getchar()!='#') 19 { 20 for(int i=1;i<=8;i++) getchar(); 21 scanf("%d%d",&tmp.id,&tmp.p); 22 tmp.px=tmp.p; 23 h[++size]=tmp; 24 push_heap(h+1,h+1+size,cmp); 25 getchar(); 26 } 27 scanf("%d",&t); 28 } 29 void go() 30 { 31 while(t--) 32 { 33 tmp=h[1]; 34 printf("%d\n",tmp.id); 35 pop_heap(h+1,h+1+size,cmp); 36 tmp.px+=tmp.p; 37 h[size]=tmp; 38 push_heap(h+1,h+1+size,cmp); 39 } 40 } 41 int main() 42 { 43 read(); 44 go(); 45 system("pause"); 46 return 0; 47 }