♐ CSP_J 组真题
2021年
4. 小熊的果篮

线上OJ

洛谷:https://www.luogu.com.cn/problem/P7912 (opens in a new tab)
acwing:https://www.acwing.com/problem/content/4092/ (opens in a new tab)
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=2077 (opens in a new tab)

核心思想:

由于题中的 水果排成一排 ,且 从左到右依次排列 ,所以可以考虑把 水果 0 的编号都放在一个 set[0] 里水果 1 的编号都放在 set[1] 里 。然后每次取水果的时候就从 set[0] 和 set[1] 中 交替取数 就好。
取数时满足基本规则如下:

  1. 如果 set[0] 和 set[1]都空了,则取数完成
  2. 如果 set[0] 和 set[1]有一个空了,则只能从另一个set中取数
  3. 如果 set[0] 和 set[1]都非空,则在set[0] 和 set[1]中 交替取数。取数前 先判断哪个set的第一个编号最小从最小的开始 取(这样的话取数就 符合水果从左到右排列 ,同时可以 规避两个块需要合并 的复杂算法)
  4. 如果在交替取数过程中,发现有一个 set 空了,则本轮取数完成。可以进行下一轮的取数

分析
n = 12
水果的种类 1 1 0 0 1 1 1 0 1 1 0 0
水果的编号 1 2 3 4 5 6 7 8 9 10 11 12
则 st[0] 实际存储的都是 0 号水果,且编号为 3 4 8 11 12
st[1] 实际存储的都是 1 号水果,且编号为 1 2 5 6 7 9 10

第一轮

按照规则3,从 st[1] 开始选。当选择出 1 3 5 8 9 11 后,按照规则4,本轮取数结束。此时
st[0] 存储的0号水果剩余编号为 4 12
st[1] 存储的1号水果剩余编号为 2 6 7 10

第二轮

按照规则3,依然从 st[1] 开始选。选择出 2 4 6 12 后,按照规则4,本轮取数结束。此时
st[0] 已经 empty
st[1] 剩余 7 10

第三轮

按照规则2,此时只能从 st[1] 中选择,且选出 7以后,由于 st[0] 已空,按照规则4,本轮取数结束。此时
st[0] empty
st[1] 剩余10

第四轮

最后一轮,把 st[1] 中剩余的10 取走,就全部结束了。

💡

本方法最大的好处是:利用 交替取数(后面的索引一定比前面的大)避开了两个块需要合并的判断

题解代码:

#include <bits/stdc++.h>
#define N 200010
 
using namespace std;
 
// 本解法核心,利用存储0和1的两个set交替取数即可 
// 好处是:利用交替取数(后面的索引一定比前面的大)避开了两个块需要合并的判断 
set<int> st[2];		//st[0]:保存种类为 0的水果的编号   st[1]:保存种类为 1的水果的编号 
 
int main()
{
    int n, a, p, lastNum; 	// p 用于 st[p]。通过p=0、p=1控制 st[p]当前取数的是0号水果还是1号水果 
    cin >> n;
    
    for(int i = 1; i <= n; ++i)
    {
    	cin >> a;
		if(a == 0)  st[0].insert(i);	// 如果读入的是 0,则把对应的编号 i 存入st[0]		
		else  st[1].insert(i);			// 如果读入的是 1,则把对应的编号 i 存入st[1]
	}
	
	// 如果 st[0]和 st[1]有一个没空,就继续挑水果组织果篮,直到全部挑空 
	while(!(st[0].empty() && st[1].empty()))
	{
		// 以下判断本轮先从哪个 st开始取水果。由于题中的水果是从左到右依次摆放,所以实际取数规则是从编号小的开始取 
		if(st[0].empty())  p = 1;  		// 如果 st[0] 中已经没有 0号水果了,则直接从 st[1]中取水果			
		else if(st[1].empty())  p = 0;	// 如果 st[1] 中已经没有 1号水果了,则直接从 st[0]中取水果
		else if(*st[0].begin() > *st[1].begin())  p = 1;	// 如果 st[0]的第一个水果编号 > st[1]的第一个水果编号,则从小的开始取 
		else   p = 0;					// 否则,就从0号开始取
		 
		lastNum = -1;	// lastNum 记录上一个取走的水果编号 
		while(true)		// 如果在下一次 st[p]的搜索中已经找不到对应编号的水果,则 break。否则就在 st[0]和 st[1]中交替搜索 
		{
			set<int>::iterator it = st[p].upper_bound(lastNum);  	// 定义迭代器 it,指向在 st[p]中找到的第一个 > lastNum 数 
						   // 注意,这里用 upper_bound,不用 lower_bound,因为 lower_bound判断的是 ≥ 
			if(it == st[p].end())	// 如果it指向末尾,说明没找到,则本轮花篮组建完成可跳出while的内循环,开启下一个花篮的组建 
				break;
			
			lastNum = *it;			// 更新上一个取走的水果编号 	
			cout << lastNum << ' ';		// 则输出该水果的编号 			
			st[p].erase(lastNum);		// 在st[p]中删除该水果编号 
			
			p = (p+1) % 2;			// p从0变为1,1变为0; 
		}
		cout << endl; 
	}
    return 0;
}