线上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;
}