fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define P pair<long long int,long long int> // 需求量 , number
  4. #define F first
  5. #define S second
  6. typedef long long int ll;
  7. deque<P> q; // 記錄所有隊首
  8. priority_queue<ll,vector<ll>,greater<ll> > pq; // 記錄所有不是隊首的包子需求量
  9. ll N, a, n;
  10.  
  11. int main() {
  12. 	ios::sync_with_stdio(0);
  13. 	cin.tie(0); cout.tie(0);
  14.  
  15. 	cin>>N;
  16. 	ll num=0; // 目前人數
  17. 	ll cnt=0; // 目前發的包子數
  18. 	ll wait=0; // 等待人數
  19. 	while( N-->0 ){
  20. 		cin>>a>>n;
  21. 		if( a==1 ){
  22. 			num++;
  23. 			// 新的隊首
  24. 			if( q.empty() ){
  25. 				q.push_back({cnt+n,num});
  26. 				continue;
  27. 			}
  28. 			P p=q.back();
  29. 			if( cnt+n>=p.F ){
  30. 				q.push_back({cnt+n,num});
  31. 				continue;
  32. 			}
  33. 			// 非隊首
  34. 			if( cnt+n<p.F ){
  35. 				pq.push(cnt+n);
  36. 			}
  37. 		}
  38. 		if( a==2 ){
  39. 			cnt+=n;
  40. 			while( !pq.empty() and pq.top()<=cnt ){
  41. 				wait++;
  42. 				pq.pop();
  43. 			}
  44.  
  45. 			P p=q.front();
  46. 			if( cnt<p.F ){
  47. 				cout<<wait<<'\n';
  48. 				continue;
  49. 			}	
  50. 			// 移除隊首
  51. 			ll now_n=p.S;
  52. 			while( q.size()>1 and cnt>=p.F ){
  53. 				q.pop_front();
  54. 				p=q.front();
  55. 				wait-=(p.S-now_n-1);
  56. 				now_n=p.S;
  57. 			}
  58. 			if( cnt>=p.F and q.size()==1 ){
  59. 				q.pop_front();
  60. 				wait=0;
  61. 			}
  62.  
  63. 			cout<<wait<<'\n';
  64. 		}
  65.  
  66. 	}
  67. }
Success #stdin #stdout 0s 5428KB
comments (?)
stdin
copy 
15
1 32
1 18
1 13
1 6
2 8
2 7
1 12
2 9
1 32
2 7
2 7
1 13
2 15
1 32
2 18
stdout
copy 
1
2
3
4
0
1
0
https://ideone.com/Jax8f3
e407. 買包子 (Bun) -- 108學年度板橋高中校內資訊學科能力競賽
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!