[CSP2021]小熊的果篮（fruit）

NC229923. [CSP2021]小熊的果篮（fruit）

描述

小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $1、2、3、……、n$ 编号。连续排在一起的同一种水果称为一个“块”。

小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。

请帮小熊计算每个果篮里包含的水果。

输入描述

输入的第一行包含一个正整数 $n$ ，表示水果的数量。

输入的第二行包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为i的水果的种类， $1$ 代表苹果， $0$ 代表桔子。

输出描述

输出若干行。

第 $i$ 行表示第 $i$ 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

示例1

输入:

12
1 1 0 0 1 1 1 0 1 1 0 0

输出:

1 3 5 8 9 11
2 4 6 12
7
10

说明:

这是第一组数据的样例说明。

所有水果一开始的情况是 1 1 0 0 1 1 1 0 1 1 0 0，一共有6个块。

在第一次挑水果组成果篮的过程中，编号为 1 3 5 8 9 11 的水果被挑了出来。

之后剩下的水果是 1 0 1 1 1 0，一共4个块。

在第二次挑水果组成果篮的过程中，编号为 2 4 6 12 的水果被挑了出来。

之后剩下的水果是 1 1，只有1个块。

在第三次挑水果组成果篮的过程中，编号为 7 的水果被挑了出来。最后剩下的水果是 1，只有1个块。

在第四次挑水果组成果篮的过程中，编号为 10 的水果被挑了出来。

示例2

输入:

20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0

输出:

1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 43ms, 内存消耗: 4704K, 提交时间: 2023-07-26 20:39:47

#include <bits/stdc++.h>
using namespace std;

struct Node{
	int l, r, num;
};
Node a[200010];
queue<int> q;
int main(){	
	int i, j, k;
	int n, t;
	int pre = -1;
	Node now;
	scanf("%d", &n);
	a[0].num = -1;
	a[n + 1].num = -1;
	for(i = 1; i <= n; i ++){
		scanf("%d", &a[i].num);
		a[i].l = i - 1;
		a[i].r = i + 1;
		if(a[i].num != a[i - 1].num)
			q.push(i);
	}
	while(!q.empty()){
		j = q.size();
		for(i = 0; i < j; i ++){
			k = q.front();
			q.pop();
			printf("%d ", k);
			if(a[k].num == a[a[k].r].num && a[k].num != a[a[k].l].num)
				q.push(a[k].r);
			a[a[k].r].l = a[k].l;
			a[a[k].l].r = a[k].r;
		} 
		puts("");
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 338ms, 内存消耗: 4260K, 提交时间: 2022-10-15 14:42:01

#include<bits/stdc++.h>
using namespace std;
vector<int>b;
int a[12345678],l[12345678],r[12345678],n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i==1||a[i]!=a[i-1])b.push_back(i);
		l[i]=i-1,r[i]=i+1;
	}
	r[0]=1,l[n+1]=n,a[0]=a[n+1]=-1;
	while(r[0]!=n+1){
		vector<int>c;
		for(auto u:b){
			cout<<u<<" ";
			int x=l[u],y=r[u];
			r[x]=y,l[y]=x;	
			if(a[u]==a[y]&&a[u]!=a[x])c.push_back(y); 
		}
		cout<<endl;
		swap(b,c);
	}
}