1371：看病
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。
【输入】
第一行输入n，表示有n个操作。
对于每个操作，首先输入push或pop。
push的情况，之后会输入ai 和 bi，分别表示患者姓名和患者病情优先级。
pop后面没有输入，但需要你输出。
【输出】
对于pop的操作，输出此时还在排队人中，优先级最大的患者姓名和优先级。
表示他可以进去看病了。
如果此时没人在排队，那么输出”none”，具体可见样例。
【输入样例】
7
pop
push bob 3
push tom 5
push ella 1
pop
push zkw 4
pop
【输出样例】
none
tom 5
zkw 4
【提示】
【数据规模和约定】
1≤n≤100000，每个人的优先级都不一样，0≤优先级≤2000000000。
姓名都是小写字母组成的，长度小于20。
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. using namespace std; 5. struct node{ 6. char nm[25]; 7. int v; 8. }hp[100005]; 9. int sz; 10. void shift_up(int i){ 11. while(i>1&&hp[i/2].v<hp[i].v){ 12. swap(hp[i/2],hp[i]); 13. i=i/2; 14. } 15. } 16. void push(node x){ 17. hp[++sz]=x; 18. shift_up(sz); 19. } 20. node top(){ 21. return hp[1]; 22. } 23. void shift_down(int i){ 24. int j; 25. while(i*2<=sz){ 26. if(i*2+1<=sz&&hp[i*2+1].v>hp[i*2].v) j=i*2+1; 27. else j=i*2; 28. if(hp[j].v>hp[i].v){ 29. swap(hp[j],hp[i]);i=j; 30. } 31. else break; 32. } 33. } 34. void pop(){ 35. hp[1]=hp[sz--]; 36. shift_down(1); 37. } 38. int main() 39. { 40. int n; 41. scanf("%d",&n); 42. sz=0; 43. for(int i=1;i<=n;i++){ 44. char op[25]; 45. scanf("%s",op); 46. if(op[1]=='o'){ 47. if(sz==0){ 48. printf("none\n"); 49. continue; 50. } 51. node tmp=top(); 52. pop(); 53. printf("%s %d\n",tmp.nm,tmp.v); 54. }else { 55. node tmp; 56. scanf("%s %d",tmp.nm,&tmp.v); 57. push(tmp); 58. } 59. } 60. return 0; 61. }
