P7912 [CSP-J 2021] 小熊的果篮题解

panda-lyl / 2024-11-13 / 原文

是模拟吗？

其实是的，虽然 $1 \le n \le 2 \times 10^5$，但是队列是个好东西.

我们定义一个结构体，来存放每一个块的信息，包括类型、起点、终点，将它们放入

队列当中，再使用基于广搜的思想，先处理，再合并，所以需要用到 $2$ 个队列.

注意点

数据中可能会有块的类型全是 $1$，或者全是 $0$ 的情况，所以保险起见，特判一下.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;

int n, a[200005], p;

struct node{
	int start, end, type; // 类型，起点，终点
};

// vis[i] 表示当前水果是否被取走
bool vis[200005];

queue<node> q, q1;

bool all_1() {
	for (int i = 1; i <= n; i++) {
		if (a[i] == 0) return 0;
	}
	return 1;
}

bool all_0() {
	for (int i = 1; i <= n; i++) {
		if (a[i] == 1) return 0;
	}
	return 1;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	if (all_1() || all_0()) { // 特判全是 1 或者 0 的情况
		for (int i = 1; i <= n; i++)
			printf("%d\n", i);
		return 0;
	}
	a[n+1] = 21474836; // 设下截止点
	int s = 1;
	for (int i = 2; i <= n + 1; i++) {
		if (a[i] != a[i-1]) { // 发现新的类型
			q.push((node){s, i - 1, a[i-1]}); // 存入
			s = i; // 更新起点
		}
	}
	int cnt = n; // 水果数量
	while (cnt) {
		while (!q.empty()) {
			node f = q.front();
			q.pop();
            // 找到当前能拿水果的起点
			while (vis[f.start] && f.start <= f.end) f.start++;
            // 出界了
			if (f.start > f.end) continue;
			printf("%d ", f.start);
			cnt--; // 水果数量减少
			vis[f.start] = 1; // 当前水果被拿走了
			if (f.start == f.end) continue; // 没有能拿的
			f.start++;
			q1.push(f); // 放入合并队列
		}
		printf("\n");
		node u;
		while (!q1.empty()) {
			u = q1.front();
			q1.pop();
			while (!q1.empty()) {
				node x = q1.front();
				if (u.type == x.type) { // 相同种类
					u.end = x.end; // 合并
					q1.pop();
				}
				else break; // 否则退出(只能合并相邻的2个)
			}
			q.push(u); // 存入新的块
		}
	}
	return 0;
}