P8188 [USACO22FEB] Email Filing S

题目描述

Farmer John 在整理他的收件箱时落后了。他的屏幕布局如下：屏幕左侧是文件夹的垂直列表，右侧是邮件的垂直列表。总共有 $M$ 个文件夹，编号为 $1\dots M$（$1\le M\le 10^4$）。他的收件箱目前包含 $N$ 封邮件，编号为 $1\dots N$（$1\le N\le 10^5$）；第 $i$ 封邮件需要归档到文件夹 $f_i$（$1\le f_i\le M$）。

FJ 的屏幕很小，因此他一次只能查看 $K$ 个文件夹和 $K$ 封邮件（$1\le K\le \min (N,M)$）。初始时，他的屏幕显示左侧的文件夹 $1\dots K$ 和右侧的邮件 $1\dots K$。为了访问其他文件夹和邮件，他需要滚动这些列表。例如，如果他在文件夹列表中向下滚动一个位置，屏幕将显示文件夹 $2\dots K+1$，再向下滚动一个位置则显示文件夹 $3\dots K+2$。当 FJ 将一封邮件拖入文件夹时，该邮件会从邮件列表中消失，其后的邮件会向前移动一个位置。例如，如果当前显示的邮件是 $1,2,3,4,5$，而 FJ 将邮件 $3$ 拖入其对应的文件夹，邮件列表将显示 $1,2,4,5,6$。FJ 只能将邮件拖入其需要归档的文件夹。

不幸的是，FJ 的鼠标滚轮坏了，他只能向下滚动，不能向上滚动。唯一能实现类似向上滚动的效果是，当他查看邮件列表的最后 $K$ 封邮件时，如果他归档了其中一封邮件，邮件列表将再次显示尚未归档的最后 $K$ 封邮件，从而将最上面的邮件向上滚动一个位置。如果剩余的邮件少于 $K$ 封，则显示所有剩余的邮件。

请帮助 FJ 判断是否能够归档所有邮件。

输入格式

输入的第一行包含 $T$（$1\le T\le 10$），表示输入中的子用例数量，所有子用例都必须正确解决才能解决整个输入用例。接下来的 $T$ 行是每个子用例的输入。对于每个子用例，第一行包含 $M$、$N$ 和 $K$。第二行包含 $f_1\cdots f_N$。

保证所有子用例的 $M$ 之和不超过 $10^4$，所有子用例的 $N$ 之和不超过 $10^5$。

输出格式

输出 $T$ 行，每行包含 YES 或 NO，表示 FJ 是否能够成功归档所有邮件。

输入输出样例 #1

输入 #1

6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1

输出 #1

YES
YES
NO
YES
YES
NO

说明/提示

• 在输入 2-10 中，所有子用例的 $M$ 之和不超过 $10^3$。
• 在输入 11-12 中，没有额外限制。

C++实现

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second
const int N = 1e5 + 5;
int T, m, n, k, cnt[N], a[N], vis[N];
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	for(cin >> T; T; T--) {
		cin >> m >> n >> k;
		for(int i = 1; i <= n; i++) cnt[i] = 0, vis[i] = 0;
		deque<int> l; // 存储被跳过的邮件 
		priority_queue<pii, vector<pii>, greater<pii>> q;
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
			if(i <= k) q.push(mp(a[i], i));
			++cnt[a[i]];
		}
		int fl = 1, fr = k, fold = 1;
		while(q.size() || l.size()) {
			while(!cnt[fold] && fold < m - k + 1) ++fold;
			if(q.size() && q.top().fi >= fold && q.top().fi <= fold + k - 1) {
				--cnt[q.top().fi];
				vis[q.top().se] = true; // 记录已经放好的邮件
				q.pop();
				if(fr < n) {
					++fr;
					q.push(mp(a[fr], fr));
				}
			} else if(fr < n) { // 邮件窗口没有滑到底时模拟补位 
				++fl, ++fr;
				q.push(mp(a[fr], fr));
				l.push_back(a[fl - 1]); // 记录跳过的邮件 
			} else if((int)q.size() < k && l.size()) { // 邮件窗口滑到底之后模拟补位 
				--fl;
				q.push(mp(l.back(), fl));
				l.pop_back();
			} else break;
			while(q.size() && q.top().se < fl) q.pop(); // 保证堆顶的邮件是没有被跳过的 
			while(vis[fl]) ++fl; // 保证 fl 位置的邮件是没有放好的 
		}
		if(q.size()) cout << "NO\n";
		else cout << "YES\n";
	}

	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容