https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/M
【Accepted】
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<map> 10 using namespace std; 11 int l,n; 12 int main() 13 { 14 int T; 15 scanf("%d",&T); 16 int cas=0; 17 while(T--) 18 { 19 priority_queue<int,vector<int>,greater<int>> qr; 20 priority_queue<int> ql; 21 scanf("%d%d",&l,&n); 22 int pos=0; 23 int dir=1; 24 int ans=0; 25 for(int i=0;i<n;i++) 26 { 27 int op; 28 scanf("%d",&op); 29 if(op==0) 30 { 31 int x; 32 scanf("%d",&x); 33 if(x<pos) ql.push(x); 34 else qr.push(x); 35 } 36 else 37 { 38 if(!ql.empty()&&!qr.empty()) 39 { 40 int t1=ql.top(); 41 int t2=qr.top(); 42 if(pos-t1==t2-pos) 43 { 44 if(dir==1) 45 { 46 ans+=t2-pos; 47 qr.pop(); 48 pos=t2; 49 dir=1; 50 } 51 else 52 { 53 ans+=pos-t1; 54 ql.pop(); 55 pos=t1; 56 dir=0; 57 } 58 } 59 else if(pos-t1<t2-pos) 60 { 61 ans+=pos-t1; 62 ql.pop(); 63 pos=t1; 64 dir=0; 65 66 } 67 else if(pos-t1>t2-pos) 68 { 69 ans+=t2-pos; 70 qr.pop(); 71 pos=t2; 72 dir=1; 73 } 74 } 75 else if(!ql.empty()) 76 { 77 int t1=ql.top(); 78 ans+=pos-t1; 79 ql.pop(); 80 pos=t1; 81 dir=0; 82 } 83 else if(!qr.empty()) 84 { 85 int t2=qr.top(); 86 ans+=t2-pos; 87 qr.pop(); 88 pos=t2; 89 dir=1; 90 } 91 } 92 } 93 printf("Case %d: %d ",++cas,ans); 94 } 95 return 0; 96 }