信奥赛-刷题笔记-队列篇-T3-P2058海港和P1886单调队列

总题单

​

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

队列篇题单

P2058 [NOIP 2016 普及组] 海港

https://www.luogu.com.cn/problem/P2058

题目背景

NOIP2016 普及组 T3

题目描述

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 $i$ 艘到达的船，他记录了这艘船到达的时间 $t_i$ (单位：秒)，船上的乘客数 $k_i$，以及每名乘客的国籍 $x_{i,1},x_{i,2},\dots ,x_{i,k}$。

小K统计了 $n$ 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 $24$ 小时（$24$ 小时 $=86400$ 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 $n$ 条信息。对于输出的第 $i$ 条信息，你需要统计满足 $t_i-86400<t_p\le t_i$ 的船只 $p$，在所有的 $x_{p,j}$ 中，总共有多少个不同的数。

输入格式

第一行输入一个正整数 $n$，表示小 K 统计了 $n$ 艘船的信息。

接下来 $n$ 行，每行描述一艘船的信息：前两个整数 $t_i$ 和 $k_i$ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。

保证输入的 $t_i$ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 $t_i$ 秒到达海港。

保证 $1\le n\le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j}\le 10^5$， $1\le t_{i-1}\le t_i\le 10^9$。

其中 $\sum k_i$ 表示所有的 $k_i$ 的和。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数表示第 $i$ 艘船到达后的统计信息。

输入输出样例 #1

输入 #1

3
1 4 4 1 2 2
2 2 2 3
10 1 3

输出 #1

3
4
4

输入输出样例 #2

输入 #2

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

输出 #2

3
3
3
4

说明/提示

【样例解释 1】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $4,1,2,2$，共来自 $3$ 个不同的国家；

第二艘船在第 $2$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $4,1,2,2,2,3$，共来自 $4$ 个不同的国家；

第三艘船在第 $10$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船、第二艘船和第三艘船，共有 $4+2+1=7$ 个乘客，分别是来自国家 $4,1,2,2,2,3,3$，共来自 $4$ 个不同的国家。

【样例解释 2】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $1,2,2,3$，共来自 $3$ 个不同的国家。

第二艘船在第 $3$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $1,2,2,3,2,3$，共来自 $3$ 个不同的国家。

第三艘船在第 $86401$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船和第三艘船，共有 $2+2=4$ 个乘客，分别是来自国家 $2,3,3,4$，共来自 $3$ 个不同的国家。

第四艘船在第 $86402$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船、第三艘船和第四艘船，共有 $2+2+1=5$ 个乘客，分别是来自国家 $2,3,3,4,5$，共来自 $4$个 不同的国家。

【数据范围】

• 对于 $10\%$ 的测试点，$n=1,\sum k_i\le 10,1\le x_{i,j}\le 10,1\le t_i\le 10$。
• 对于 $20\%$ 的测试点，$1\le n\le 10,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 32767$。
• 对于 $40\%$ 的测试点，$1\le n\le 100,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 86400$。
• 对于 $70\%$ 的测试点，$1\le n\le 1000,\sum k_i\le 3000,1\le x_{i,j}\le 1000,1\le t_i\le 10^9$。
• 对于 $100\%$ 的测试点，$1\le n\le 10^5,\sum k_i\le 3\times 10^5,1\le x_{i,j}\le 10^5,1\le t_i\le 10^9$。

代码1

思路

✅ 问题回顾

需要处理 n 艘船的信息，每艘船在某个时间点到达，并带有若干乘客的国籍信息。要求：
对于每一艘船，在过去的 86400 秒（即一天） 内所有乘客中，统计有多少个不同的国家。
时间递增给出，所以可以使用滑动窗口思想。

🧠 解题思路简要说明
使用一个队列保存每一位乘客的信息（国籍 + 到达时间）
用数组 num[x] 记录当前国籍 x 出现了多少次
用变量 ans 表示当前不同国家的数量
每次加入新的乘客时更新 num[x] 和 ans
同时检查队列头部是否有超过 86400 秒的乘客，若有则移除并更新计数

📌 注释解释关键词

变量/结构	含义
num[x]	国籍 x 在当前窗口中的出现次数
ans	当前窗口中不同国家的数量
q	存储所有乘客的队列，用于维护时间窗口
node{x, t}	表示一位乘客，国籍是 x，到达时间是 t
while (!q.empty() && q.front().t + 86400 <= t)	检查队列头部是否已过期（超过一天）

#include <bits/stdc++.h>
using namespace std;int n, ans, num[100005]; // num[x]: 国籍 x 当前出现的次数；ans: 不同国家总数// 定义结构体 node：记录每位乘客的国籍和到达时间
struct node {int x, t; // x: 国籍，t: 到达时间
} h;queue<node> q; // 队列模拟滑动窗口，先进先出int main() {cin >> n; // 输入 n 艘船的信息for (int i = 1, t, k; i <= n; i++) {cin >> t >> k; // 当前船的到达时间 t 和乘客数量 k// 处理当前船上每一位乘客for (int j = 1, x; j <= k; j++) {cin >> x;q.push({x, t}); // 将该乘客入队if (++num[x] == 1) ans++; // 如果这是这个国家第一次出现，ans++}// 清理过期的乘客（距离当前时间超过 86400 秒的）while (!q.empty() && q.front().t + 86400 <= t) {h = q.front(); q.pop(); // 取出并删除队头元素if (--num[h.x] == 0) ans--; // 如果这个国家的所有人都被清空了，ans--}// 输出当前活跃的不同国家数cout << ans << '\n';}return 0;
}

代码2 用map统计

#include <bits/stdc++.h>
using namespace std;int n, ans;
map<int, int> num; // map<国籍, 出现次数>struct node {int x, t; // x: 国籍，t: 到达时间
};queue<node> q;int main() {cin >> n; // 输入 n 艘船的信息for (int i = 1, t, k; i <= n; i++) {cin >> t >> k; // 当前船的到达时间 t 和乘客数量 k// 处理当前船上每一位乘客for (int j = 1, x; j <= k; j++) {cin >> x;q.push({x, t}); // 将该乘客入队if (num[x] == 0) ans++; // 如果这是第一次出现这个国家num[x]++; // 增加该国籍的计数}// 清理过期的乘客（距离当前时间超过 86400 秒的）while (!q.empty() && q.front().t + 86400 <= t) {node h = q.front(); q.pop();num[h.x]--; // 减少该国籍的计数if (num[h.x] == 0) ans--; // 如果这个国家已经没有乘客了，ans 减一}// 输出当前活跃的不同国家数cout << ans << '\n';}return 0;
}

P1886 滑动窗口 /【模板】单调队列

https://www.luogu.com.cn/problem/P1886

题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k=3$，有如下过程：

$$\begin{array}{ccc}\text{窗口位置}& \text{最小值}& \text{最大值}\\ \text{[1 3 -1] -3 5 3 6 7 }& -1& 3\\ \text{ 1 [3 -1 -3] 5 3 6 7 }& -3& 3\\ \text{ 1 3 [-1 -3 5] 3 6 7 }& -3& 5\\ \text{ 1 3 -1 [-3 5 3] 6 7 }& -3& 5\\ \text{ 1 3 -1 -3 [5 3 6] 7 }& 3& 6\\ \text{ 1 3 -1 -3 5 [3 6 7]}& 3& 7\end{array}$$

输入格式

输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例 #1

输入 #1

8 3
1 3 -1 -3 5 3 6 7

输出 #1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 $50\%$ 的数据，$1\le n\le 10^5$；
对于 $100\%$ 的数据，$1\le k\le n\le 10^6$，$a_i\in [-2^{31},2^{31})$。

代码1

#include<cstdio>
#include<cstring>
using namespace std; struct Monotone_queue
{static const int maxn=1000001;int n,k,a[maxn];int q[maxn],head,tail,p[maxn];//同题目叙述一样，q是单调队列，p是对应编号。void read(){scanf("%d %d",&n,&k);for(int i=1;i<=n;++i)scanf("%d",&a[i]);}//读入不必说了void monotone_max()//单调最大值{head=1;tail=0;for(int i=1;i<=n;++i){while(head<=tail&&q[tail]<=a[i])tail--;q[++tail]=a[i];p[tail]=i;while(p[head]<=i-k)head++;if(i>=k)printf("%d ",q[head]);}printf("\n");}void monotone_min(){head=1;tail=0;//为啥要这样呢?因为head要严格对应首元素，tail要严格对应尾元素，所以当tail>=head时，说明有元素。而一开始队列为空，说一要这样赋值。其实这跟普通队列一样。for(int i=1;i<=n;++i){//a[i]表示当前要处理的值while(head<=tail&&q[tail]>=a[i])tail--;//只要队列里有元素，并且尾元素比待处理值大，即表示尾元素已经不可能出场，所以出队。直到尾元素小于待处理值，满足"单调"。q[++tail]=a[i];//待处理值入队。p[tail]=i;//同时存下其编号while(p[head]<=i-k)head++;//如果队首元素已经"过时"，出队。if(i>=k)printf("%d ",q[head]);//输出最值，即队首元素。i>=k表示该输出，至于why就自己看题目。}printf("\n");}
}worker;int main()
{worker.read();worker.monotone_min();worker.monotone_max();return 0;
}

#include <cstdio>
#include <cstring>using namespace std;// 定义一个结构体来封装整个问题的变量和函数
struct Monotone_queue {// 常量定义：数组最大长度为 1e6 + 1static const int maxn = 1000001;// 输入相关变量int n, k;           // n: 数组长度；k: 滑动窗口大小int a[maxn];        // 存储输入的数组// 单调队列相关变量int q[maxn];        // q[] 是单调队列，保存的是可能成为最值的候选元素int p[maxn];        // p[i] 表示队列中第 i 个元素在原数组中的下标（位置）int head, tail;     // head 和 tail 分别是队列的头部和尾部指针/*** 读取输入数据*/void read() {// 输入 n 和 kscanf("%d %d", &n, &k);// 输入数组 a[1..n]for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);}/*** 使用单调队列找出每个滑动窗口中的最小值*/void monotone_min() {// 初始化队列头尾指针head = 1;tail = 0;// 遍历数组中每一个元素for (int i = 1; i <= n; ++i) {// 维护单调递增队列（队列中保存的是当前窗口可能的最小值）while (head <= tail && q[tail] >= a[i])tail--;// 将当前元素加入队列尾部q[++tail] = a[i];p[tail] = i;  // 同时记录该元素的位置// 如果队首元素已经不在当前窗口内，则移除它while (p[head] <= i - k)head++;// 当窗口长度达到 k 时才输出结果if (i >= k)printf("%d ", q[head]);}printf("\n"); // 每一行输出结束后换行}/*** 使用单调队列找出每个滑动窗口中的最大值*/void monotone_max() {// 初始化队列头尾指针head = 1;tail = 0;// 遍历数组中每一个元素for (int i = 1; i <= n; ++i) {// 维护单调递减队列（队列中保存的是当前窗口可能的最大值）while (head <= tail && q[tail] <= a[i])tail--;// 将当前元素加入队列尾部q[++tail] = a[i];p[tail] = i;  // 同时记录该元素的位置// 如果队首元素已经不在当前窗口内，则移除它while (p[head] <= i - k)head++;// 当窗口长度达到 k 时才输出结果if (i >= k)printf("%d ", q[head]);}printf("\n"); // 每一行输出结束后换行}
} worker; // 创建一个结构体对象/*** 主函数入口*/
int main() {worker.read();         // 读取输入数据worker.monotone_min(); // 输出每个窗口的最小值worker.monotone_max(); // 输出每个窗口的最大值return 0;
}

代码2

#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>using namespace std;// 定义一个结构体来封装整个问题的变量和函数
struct MonotoneQueue {int n, k;vector<int> a; // 存储输入数组// 双端队列保存的是元素的索引（不是值），这样更容易判断是否出界deque<int> dq; // 双端队列// 构造函数初始化数据MonotoneQueue() {scanf("%d %d", &n, &k);a.resize(n + 1); // 下标从 1 开始，方便处理逻辑for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);}/*** 求每个滑动窗口的最小值*/void getMin() {dq.clear(); // 清空队列for (int i = 1; i <= n; ++i) {// 1. 移除队列中所有比当前元素大的值（它们不可能是最小值）while (!dq.empty() && a[dq.back()] >= a[i])dq.pop_back();// 2. 将当前元素加入队列尾部dq.push_back(i);// 3. 移除队列头部已经不在窗口范围内的元素while (dq.front() <= i - k)dq.pop_front();// 4. 当窗口长度达到 k 后开始输出结果if (i >= k)printf("%d ", a[dq.front()]);}printf("\n");}/*** 求每个滑动窗口的最大值*/void getMax() {dq.clear(); // 清空队列for (int i = 1; i <= n; ++i) {// 1. 移除队列中所有比当前元素小的值（它们不可能是最大值）while (!dq.empty() && a[dq.back()] <= a[i])dq.pop_back();// 2. 将当前元素加入队列尾部dq.push_back(i);// 3. 移除队列头部已经不在窗口范围内的元素while (dq.front() <= i - k)dq.pop_front();// 4. 当窗口长度达到 k 后开始输出结果if (i >= k)printf("%d ", a[dq.front()]);}printf("\n");}
};int main() {MonotoneQueue mq; // 创建对象自动读取输入mq.getMin();      // 输出每个窗口的最小值mq.getMax();      // 输出每个窗口的最大值return 0;
}

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：FILE freopen( const char path, const char mode, FILE stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}