线上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] 中 交替取数 就好。
取数时满足基本规则如下:
- 如果 set[0] 和 set[1]都空了，则取数完成
- 如果 set[0] 和 set[1]有一个空了，则只能从另一个set中取数
- 如果 set[0] 和 set[1]都非空，则在set[0] 和 set[1]中 交替取数。取数前 先判断哪个set的第一个编号最小， 从最小的开始 取（这样的话取数就
符合水果从左到右排列，同时可以规避两个块需要合并的复杂算法） - 如果在交替取数过程中，发现有一个 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;
}