0x12 队列

小组队列

有 个小组要排成一个队列，每个小组中有若干人。
当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。
请你编写一个程序，模拟这种小组队列。
输入格式：
输入将包含一个或多个测试用例。
对于每个测试用例，第一行输入小组数量 。
接下来 行，每行输入一个小组描述，第一个数表示这个小组的人数，接下来的数表示这个小组的人的编号。
编号是 到 范围内的整数。
一个小组最多可包含 个人。
最后，命令列表如下。 有三种不同的命令：
1、ENQUEUE x - 将编号是 的人插入队列；
2、DEQUEUE - 让整个队列的第一个人出队；
3、STOP - 测试用例结束
每个命令占一行。
当输入用例 时，代表停止输入。
需注意：测试用例最多可包含 （ 万）个命令，因此小组队列的实现应该是高效的：
入队和出队都需要使用常数时间。
输出样例
对于每个测试用例，首先输出一行 Scenario #k，其中 是测试用例的编号。
然后，对于每个 DEQUEUE 命令，输出出队的人的编号，每个编号占一行。
在每个测试用例（包括最后一个测试用例）输出完成后，输出一个空行。
数据范围

输入样例：

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

输出样例：

Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001

队列模拟（大队列套小队列）
可以使用 STL 来优化编码

#include<bits/stdc++.h>
using namespace std;
void solve(int n) {
    unordered_map<int, int> id, in;
    vector<queue<int>> q(n + 1);
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        int cnt, y;
        scanf("%d", &cnt);
        for(int j = 1; j <= cnt; j++){
            scanf("%d", &y);
            id[y] = i;
        }
    }
    string o;
    while(cin >> o) {
        if(o[0] == 'E') {
            int x; scanf("%d", &x);
            if(in.count(id[x])) {
                q[id[x]].push(x);
            } else {
                Q.push(id[x]);
                q[id[x]].push(x);
                in[id[x]] = 1;
            }
        } else if(o[0] == 'D') {
            int qid = Q.front();
            printf("%d\n", q[qid].front());
            q[qid].pop();
            if(q[qid].size() == 0) {
                Q.pop();
                in.erase(qid);
            }
        } else {
            break;
        }
    }
    puts("");
}
int main(){
    int n, cas = 0;
    while(~scanf("%d", &n) && n) {
        printf("Scenario #%d\n", ++cas);
        solve(n);
    }
}

蚯蚓

蛐蛐国最近蚯蚓成灾了！
隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 只蚯蚓，第 只蚯蚓的长度为 ，所有蚯蚓的长度都是非负整数，即可能存在长度为 的蚯蚓。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。
若有多只最长的，则任选一只。
神刀手切开蚯蚓的位置由有理数 决定。
一只长度为 的蚯蚓会被切成两只长度分别为 和 的蚯蚓。
特殊地，如果这两个数的其中一个等于 ，则这个长度为 的蚯蚓也会被保留。
此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数 。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。
蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 秒才能到来。
蛐蛐国王希望知道这 秒内的战况。
具体来说，他希望知道：

1. 秒内，每一秒被切断的蚯蚓被切断前的长度，共有 个数。
2. 秒后，所有蚯蚓的长度，共有 个数。

输入格式
第一行包含六个整数 ，其中： 的意义参考题目描述； 均为正整数；你需要自己计算 （保证 ）； 是输出参数，其含义将会在输出格式中解释。
第二行包含 个非负整数，为 ，即初始时 只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。

输出格式
第一行输出 个整数，按时间顺序，依次输出第 秒，第 秒，第 秒，……被切断蚯蚓（在被切断前）的长度。
第二行输出 %2Ft%E2%8C%8B#card=math&code=%E2%8C%8A%28n%2Bm%29%2Ft%E2%8C%8B&id=VTr1q) 个整数，输出 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 ，第 ，第 ，……的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。
数据范围
,
,
,
,
,
,

输入样例：

3 7 1 1 3 1
3 3 2

输出样例：

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

样例解释
样例中，在神刀手到来前： 只蚯蚓的长度为 。
秒后：一只长度为 的蚯蚓被切成了两只长度分别为 和 的蚯蚓，其余蚯蚓的长度增加了 。最终 只蚯蚓的长度分别为 %2C4%2C3#card=math&code=%281%2C2%29%2C4%2C3&id=YMxPi)。 括号表示这个位置刚刚有一只蚯蚓被切断。
秒后：一只长度为 的蚯蚓被切成了 和 。 只蚯蚓的长度分别为：%2C4#card=math&code=2%2C3%2C%281%2C3%29%2C4&id=v32h5)。
秒后：一只长度为 的蚯蚓被切断。 只蚯蚓的长度分别为：#card=math&code=3%2C4%2C2%2C4%2C%281%2C3%29&id=bzlrP)。
秒后：一只长度为 的蚯蚓被切断。 只蚯蚓的长度分别为：%2C3%2C5%2C2%2C4#card=math&code=4%2C%281%2C3%29%2C3%2C5%2C2%2C4&id=MjOps)。
秒后：一只长度为 的蚯蚓被切断。 只蚯蚓的长度分别为：%2C3%2C5#card=math&code=5%2C2%2C4%2C4%2C%281%2C4%29%2C3%2C5&id=cZP6M)。
秒后：一只长度为 的蚯蚓被切断。 只蚯蚓的长度分别为：%2C3%2C5%2C5%2C2%2C5%2C4%2C6#card=math&code=%281%2C4%29%2C3%2C5%2C5%2C2%2C5%2C4%2C6&id=Tfzqt)。
秒后：一只长度为 的蚯蚓被切断。 只蚯蚓的长度分别为：#card=math&code=2%2C5%2C4%2C6%2C6%2C3%2C6%2C5%2C%282%2C4%29&id=djYwN)。
所以， 秒内被切断的蚯蚓的长度依次为 。
秒后，所有蚯蚓长度从大到小排序为 。

该题是 NOIP2016 提高组的 D2T2
直接用优先队列做可以得85分。
注意到最一开始的元素从小到大按比例分割之后，大小顺序依旧保留，只是被分成了左右两个部分。
比如 ，被分成了，被分成了 ，那么仍然有
对于分割之后的，用两个队列维护即可。
总体复杂度

#include<bits/stdc++.h>
using namespace std;
const int N=100010, inf = 1e9;
int n, m, u, v, q, t;
int a[N];
queue<int> q1, q2, q3;
int get(){
    int x, a, b, c;
    a = b = c = -inf;
    if(q1.size()) a = q1.front();
    if(q2.size()) b = q2.front();
    if(q3.size()) c = q3.front();
    x = max({a, b, c});
    if(x == a) q1.pop();
    else if(x == b) q2.pop();
    else if(x == c) q3.pop();
    return x;
}
int main(){
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + 1 + n, greater<int>());
    for(int i=1;i<=n;i++) q1.push(a[i]);
    for(int i=1;i<=m;i++){
        int x = get();
        x += (i - 1) * q;
        if(i % t == 0) printf("%d ", x);
        int l = 1ll * x * u / v;
        int r = x - l;
        // printf("%d %d\n", l, r);
        q2.push(l - i * q);
        q3.push(r - i * q);
    }
    puts("");
    for(int i=1;i<=n+m;i++){
        int x = get() + m * q;
        if(i % t == 0) printf("%d ", x);
    }
    puts("");
}

双端队列

达达现在碰到了一个棘手的问题，有 个整数需要排序。
达达手头能用的工具就是若干个双端队列。
她从 到 需要依次处理这 个数，对于每个数，达达能做以下两件事：
1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2．将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。
请你求出最少需要多少个双端序列。
输入格式
第一行输入整数 ，代表整数的个数。
接下来 行，每行包括一个整数 ，代表所需处理的整数。
输出格式
输出一个整数，代表最少需要的双端队列数。
数据范围

输入样例：

6
3
6
0
9
6
3

输出样例：

2

此题难度较大。
例如序列 [3, 6, 0, 9, 6, 3]，给每个数字组合成一个 pair，分别表示值和所在下标。
排序后可得：[(0,3), (3,1), (3, 6), (6, 2), (6, 5), (9, 4)]
容易想到：对于值相同的一段，在双端队列中应当是连续的，那么上述数组可以按值划分成若干段：[0, 3, 6, 9]，其中 0 的出现坐标是 3, 3出现的坐标是 1 和 6。
在顺序遍历过程中，往双端队列中添加元素，最终队列中的元素下标一定是先递减再递增的。所以我们希望这样的下标规律也尽可能的在最终排好序的序列中。
由于 3 在 1 和 6 中都出现了，所以最终在队列中 1 和 6 必须挨着。我们可以按照 1、6 的顺序将其添加到队列尾部，或者按照 1、6 的顺序将其添加到队列的首部，这样都是符合要求的。只要最终队列中的坐标是先递减再递增即可。
由此，我们可以翻转等值元素的 pos 区间。记录等值元素出现的最小位置以及最大位置，然后从小到大遍历每个元素，尝试将当前区间翻转或者不翻转，使得坐标变化的低谷个数最少。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int,int>> a(n + 1);
    for(int i = 1; i <= n ;i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a.begin() + 1, a.end());
    vector<int> l, r;
    l.emplace_back(a[1].second);
    for(int i = 1; i < n; i++){
        if(a[i].first != a[i + 1].first) {
            r.emplace_back(a[i].second);
            l.emplace_back(a[i + 1].second);
        }
    }
    r.emplace_back(a[n].second);
    // 第 i 段等值区间为 [l[i], r[i]]
    // f = false 表示现在遍历过程中处于递减状态，由于我们希望低谷最少，所以起初设置为递减状态是较优的。
    bool f = false;
    int h = 1E9, rs = 0;
    for(int i = 0; i < l.size(); i++){
        if(f) { 
            // 处于递增状态
            if(l[i] > h) {
                // 递增状态无需变化
                h = r[i];
            } else {
                // 递增状态打破，[l[i], r[i]] 区间翻转
                h = l[i];
                f = false;
            }
        } else {
            // 处于递减状态
            if(r[i] < h) {
                // 递减状态无需变化
                h = l[i];
            } else {
                h = r[i];
                rs ++;
                f = true;
            }
        }
    }
    // 最后的那部分处于递减的区间，也需要一个新的双端队列来处理
    if(f == false) rs ++;
    printf("%d\n", rs);
    return 0;
}

最大子序和

输入一个长度为 的整数序列，从中找出一段长度不超过 的连续子序列，使得子序列中所有数的和最大。
注意： 子序列的长度至少是 。
输入格式
第一行输入两个整数 。
第二行输入 个数，代表长度为 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数，代表该序列的最大子序和。
数据范围

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

s[i] 表示前 i 项的和，则连续子序列 [L,R] 中数的和就等于 s[R]-s[L-1]。
原问题转换为：找出两个位置 x,y，使得 s[y]-s[x] 最大并且y-x < m。
枚举右端点 i，当 i 固定时，问题变为：找到一个左端点 j，其中 并且 s[j] 最小。
不妨比较任意两个位置 j 和 k，如果 k < j < i 并且 s[k] > s[j]，那么对于所有大于等于 i 的右端点，k 永远不会成为最优选择。
所以，可能成为最优选择的策略集合一定是一个下标位置递增，对应的前缀和 S 的值也递增的序列。
我们可以用一个队列来保存这个序列，随着右端点从前向右扫描，对于每个 i 执行以下操作：

1. 判断队头决策与 i 的距离是否超过 M 的范围，若超出则出队。
2. 此时队头就是右端点为 i 时，左端点 j 的最优选择。
3. 不断删除队尾决策，直到队尾对应的 S 值小于 s[i]。然后把 i 作为一个新的决策入队。

   #include <bits/stdc++.h>
   using namespace std;
   const int N = 300010;
   typedef long long ll;
   ll a[N],sum[N];
   int q[N],l,r;
   int n,m;
   int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    l = 0,r = -1;
    q[++r] = 0;
    ll res = 0;
    for(int i=1;i<=n;i++){
        while(l <= r && i - q[l] > m)l++;
        res = max(res,sum[i] - sum[q[l]]);
        while(l <= r && sum[i] <= sum[q[r]])r--;
        q[++r] = i;
    }
    cout << res << endl;
    return 0;
   }