存在一个队列,给定
1 x c
,表示向队尾插入
2 c
,表示从队头取出
大概也算是个语法题?
维护一个队列,里面元素是个 pair < int, int >
记录元素值和数量,{x, c}
,Split
的操作,然后对应维护一下
对于
xxxxxxxxxx
641
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template< typename T = int >
24inline T read(void);
25
26queue < pair < int, int >/*value, cnt*/ > balls;
27
28int main(){
29 int N = read();
30 while(N--){
31 int opt = read();
32 if(opt == 1){
33 int x = read(), c = read();
34 balls.push({x, c});
35 }else{
36 ll ans(0);
37 int c = read();
38 while(c > 0 && !balls.empty()){
39 auto tp = balls.front();
40 if(c >= tp.second)balls.pop(), c -= tp.second, ans += (ll)tp.first * tp.second;
41 else ans += (ll)c * tp.first, balls.front().second -= c, c = 0;
42 }printf("%lld\n", ans);
43 }
44 }
45
46 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47 return 0;
48}
49
50template < typename T >
51inline T read(void){
52 T ret(0);
53 short flag(1);
54 char c = getchar();
55 while(c != '-' && !isdigit(c))c = getchar();
56 if(c == '-')flag = -1, c = getchar();
57 while(isdigit(c)){
58 ret *= 10;
59 ret += int(c - '0');
60 c = getchar();
61 }
62 ret *= flag;
63 return ret;
64}
update-2022_10_24 初稿