队列

队列是一种先进先出的线性数据结构
一般来说，元素从右端（队尾）入队，从左端（队头）出队
可以将队头队尾相连，优化空间利用，这就是“循环队列”
一般直接用STL就好啦

模板

  1. // 普通队列
  2. // hh 表示队头，tt表示队尾
  3. int q[N], hh = 0, tt = -1;
  5. // 向队尾插入一个数
  6. q[ ++ tt] = x;
  8. // 从队头弹出一个数
  9. hh ++ ;
  11. // 队头的值
  12. q[hh];
  14. // 判断队列是否为空
  15. if (hh <= tt)
  16. {
  18. }
  20. // 循环队列
  21. // hh 表示队头，tt表示队尾的后一个位置
  22. int q[N], hh = 0, tt = 0;
  24. // 向队尾插入一个数
  25. q[tt ++ ] = x;
  26. if (tt == N) tt = 0;
  28. // 从队头弹出一个数
  29. hh ++ ;
  30. if (hh == N) hh = 0;
  32. // 队头的值
  33. q[hh];
  35. // 判断队列是否为空
  36. if (hh != tt)
  37. {
  39. }

题目

小组队列

这题需要两组队列，一组队列用于维护各个小组，另外一组用于维护小组间的顺序
用哈希表存储每个人对应的小组序号
剩下的按照题意模拟即可

  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_map>
  4. #include <string>
  6. using namespace std;
  8. const int N = 1010;
  9. unordered_map<int, int> rec;
  11. int main() {
  12.     int n, no = 1;
  13.     while (cin >> n, n) {
  14.         printf("Scenario #%d\n", no++);
  16.         for (int i = 0; i < n; i++) {
  17.             int cnt;
  18.             scanf("%d", &cnt);
  19.             for (int j = 0; j < cnt; j++) {
  20.                 int x;
  21.                 scanf("%d", &x);
  22.                 rec[x] = i;    // 哈希：人对应的小组编号
  23.             }
  24.         }
  26.         queue<int> team[N];
  27.         queue<int> all;
  29.         string op;
  30.         while (cin >> op, op != "STOP") {
  31.             if (op == "ENQUEUE") {
  32.                 int x;
  33.                 scanf("%d", &x);
  35.                 int tid = rec[x];
  36.                 if (team[tid].empty()) all.push(tid);
  37.                 team[tid].push(x);
  38.             }
  39.             else {
  40.                 int tid = all.front();
  41.                 int x = team[tid].front();
  42.                 team[tid].pop();
  43.                 printf("%d\n", x);
  45.                 if (team[tid].empty()) all.pop();
  46.             }
  47.         }
  48.         putchar('\n');
  49.     }
  51.     return 0;
  52. }

蚯蚓

这题要求维护一个集合，支持查询最大值、删除最大值、插入新的值，可以考虑使用二叉堆
对于其余蚯蚓每个长度增加q，可以转化成新增蚯蚓的长度减去q，再用一个变量维护整个过程中长度增加总和
上面是常规做法，但是这题数据量大，要求每次操作是O(1)的，这就需要挖掘题目中的规律
简单说就是，如果我们按照长度从大到小取出数，新产生的数也会按照时间递减
这样一来只要用三个队列，每个从三个队头挑出最大的那个就行

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <limits.h>
  5. using namespace std;
  7. typedef long long LL;
  9. const int N = 7e6 + 10;
  11. int a[N], l[N], r[N];
  12. int hha = 0, hhl = 0, hhr = 0, tta = -1, ttl = -1, ttr = -1;
  13. int n, m, q, u, v, t;
  15. int get_max() {
  16.     int res = INT_MIN;
  18.     if (tta >= hha) res = max(res, a[hha]);
  19.     if (ttl >= hhl) res = max(res, l[hhl]);
  20.     if (ttr >= hhr) res = max(res, r[hhr]);
  22.     if (tta >= hha && res == a[hha]) hha++;
  23.     else if (ttl >= hhl && res == l[hhl]) hhl++;
  24.     else hhr++;
  26.     return res;
  27. }
  29. int main() {
  30.     // cin >> n >> m >> q >> u >> v >> t;
  31.     scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
  33.     for (int i = 0; i < n; i++) {
  34.         int x;
  35.         scanf("%d", &x);
  36.         a[++tta] = x;
  37.     }
  38.     sort(a, a + n);
  39.     reverse(a, a + n);
  41.     int delta = 0;
  43.     for (int i = 1; i <= m; i++) {
  44.         int x = get_max();
  45.         x += delta;
  46.         if (i % t == 0) printf("%d ", x);
  48.         delta += q;
  49.         int left = 1ll * x * u / v, right = x - left;
  50.         l[++ttl] = left - delta, r[++ttr] = right - delta;
  51.     }
  53.     putchar('\n');
  55.     for (int i = 1; i <= n + m; i++) {
  56.         int x = get_max();
  57.         if (i % t == 0) printf("%d ", x + delta);
  58.     }
  60.     return 0;
  61. }

双端队列

名叫双端队列但是关系不大的一道题
考虑这样一种情况，不幸将PQ放入同一个队列，后面出现介于PQ之间的数，直接完蛋
这启发我们从数值大小而非输入顺序去考虑
可以先把数组从小到大排序，然后根据原始下标分成尽量少的几段，每一段对应一个双端队列
双端队列对于数据的要求是满足单谷性质（先单减后单增），这样一来队列可以从中间向两边扩展（建议画图）
我们要做的就是根据原始下标大小找出最少的单谷数目
操作空间主要在于连续几个相等的数可以重新排序，这里采用贪心策略，尽量保持上一段的单调性

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <limits.h>
  5. using namespace std;
  7. typedef pair<int, int> PII;
  9. const int N = 2e5 + 10;
  11. PII a[N];
  13. int main() {
  14.     int n;
  15.     cin >> n;
  16.     for (int i = 1; i <= n; i++) {
  17.         scanf("%d", &a[i].first);
  18.         a[i].second = i;
  19.     }
  21.     sort(a + 1, a + n + 1);
  23.     int last = INT_MAX, ans = 1, dir = -1;
  24.     int i = 1;
  25.     while (i <= n) {
  26.         int j = i;
  27.         while (a[++j].first == a[i].first);
  29.         int minp = a[i].second, maxp = a[j - 1].second;
  31.         if (dir == -1) {
  32.             if (maxp < last) {
  33.                 last = minp;
  34.             }
  35.             else {
  36.                 dir = 1;
  37.                 last = maxp;
  38.             }
  39.         }
  40.         else {
  41.             if (minp > last) {
  42.                 last = maxp;
  43.             }
  44.             else {
  45.                 last = minp;
  46.                 dir = -1;
  47.                 ans++;
  48.             }
  49.         }
  51.         i = j;
  52.     }
  54.     cout << ans;
  56.     return 0;
  57. }