算法竞赛进阶指南 基本数据结构 0x12队列

元素进行多次入队、出队后，用于实现队列结构的 数组 的开头部分空间就会被严重浪费，所以我们经常将其优化为“循环队列”，也就是把队列看作一个首尾相接的环，只要队列中的元素个数在任意时刻都不超过环长，那么随着入队和出队 *** 作的进行，存储元素的那一段位置就像沿着环不停地移动，重复利用着历史上曾被占用过的空间。C++ STL中的queue就是一个循环队列，也是我们在代码中最常见的队列实现方式。

队列也是实现 广度优先搜素 的基本结构。

0、AcWing 132. 小组队列

题意 ：

• 有 n 个小组要排成一个队列，每个小组中有若干人。
• 当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。
• 请你编写一个程序，模拟这种小组队列。
• 需注意：测试用例最多可包含 200000（20 万）个命令，因此小组队列的实现应该是高效的：入队和出队都需要使用常数时间。
• 1≤n≤1000

思路 ：

• 因为在任何时刻，同一个小组的人只要来到了队伍，就会站在一起，所以建立一个队列team存储队伍中素有小组的编号，再为每个小组分别建立一个队列存储队伍中这个小组的所有成员，一共n+1个队列

#include 
#include 
using namespace std;
const int N = 1e6 + 10;

int a[N];

int main() {
    int n;
    int cnt = 1;
    while (cin >> n, n) {
        printf("Scenario #%d\n", cnt ++ );
        for (int i = 1, k; i <= n; ++ i) {
            cin >> k;
            for (int j = 1, x; j <= k; ++ j) {
                cin >> x;
                a[x] = i;
            }
        }
        
        queue<int> q0, q[n + 1];
        
        string op;
        int x;
        while (cin >> op) {
            if (op[0] == 'E') {
                cin >> x;
                int t = a[x];
                if (q[t].empty()) q0.push(t);
                q[t].push(x);
            } else if (op[0] == 'D') {
                int t = q0.front();
                cout << q[t].front() << endl;
                q[t].pop();
                if (q[t].empty()) q0.pop();
            } else {
                break;
            }
        }
        cout << endl;
    }
}

1、（跳）AcWing 133. 蚯蚓 单调队列 0、AcWing 135. 最大子序和

题意 ：

• 输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
• 注意： 子序列的长度至少是 1。

思路 ：

• 计算“区间和”的问题，一般转化为“两个前缀和相减”的形式进行求解。我们先求出S[i]表示序列前i项和，那么原序列可以转化为：找出两个位置x，y，使 S [ y ] − S [ x ] S[y]-S[x] S[y]−S[x]最大并且 y − x ≤ M y-x \leq M y−x≤M
• 首先我们枚举右端点i，当i固定时，问题就变为：找到一个左端点j，其中 j ∈ [ i − m , i − 1 ] j \in [i-m,i-1] j∈[i−m,i−1]并且 S[j]最小
• 不妨比较一下任意两个位置j和k，如果 k < j < i kk<j<i并且 S [ k ] ≥ S [ j ] S[k] \geq S[j] S[k]≥S[j]，那么对于所有大于等于i的右端点，k永远不会成为最优选择。这是因为不但S[k]不小于S[j]，而且j离i更近，长度更不容易超过M，即j的生存能力比k更强。所以当j出现后，k就完全是一个无用的位置。
• 以上比较告诉我们，可能成为最优选择的策略集合一定是一个“下标位置递增、对应的前缀和S的值也递增”的序列。我们可以用一个队列保存这个序列。随着右端点变从前向后扫描，我们对每个i执行以下三个步骤：
  1、判断队头决策与i的距离是否超出M的范围，若超出则出队
  2、此时队头就是右端点为i时，左端点j的最优选择
  3、不断删除队尾决策，直到队尾对应的S值小于S[i]。然后把i作为一个新的决策入队。
• 这就是著名的单调队列算法，因为每个元素至多入队一次、出队依次，所以整个算法的时间复杂度是O(N)。它的思想也是 在决策集合（队列）中及时排除一定不是最优解的选择。单调队列是优化动态规划的一个重要手段，我们在0x59节会详细讲解。

细节：

• 使用前缀和的话下标要从1开始
• 手写队列

#include 
using namespace std;
const int N = 3e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int a[N], s[N], q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    
    int ans = -INF;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++ i) {
        if (q[hh] + m < i) ++ hh;
        ans = max(ans, s[i] - s[q[hh]]);
        while (hh <= tt && s[q[tt]] >= s[i]) -- tt;
        q[ ++ tt] = i;
    }
    printf("%d", ans);
}