简答题
偏难
#22115
小熊的果篮
小熊的果篮

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int> s1, s2; // 存储两种下标的集合
int main() {
scanf("%d", &n);
s1.clear();
s2.clear();
int q;
for (int i = 1; i <= n; ++i) {
scanf("%d", &q);
if (q) {
s1.insert(i); // q为1时插入s1
} else {
s2.insert(i); // q为0时插入s2
}
}
// 插入INF防止set为空时操作出错
s1.insert(INF);
s2.insert(INF);
int nw = 0;
// p表示当前要操作的集合:0为s1,1为s2(选择最小下标的集合)
bool p = (*s1.begin() < *s2.begin()) ? 0 : 1;
// 循环处理,直到当前操作的集合只剩下INF(size > 1表示还有有效元素)
while ((!p && s1.size() > 1) || (p && s2.size() > 1)) {
if (!p) { // 处理s1
nw = *s1.upper_bound(nw); // 找nw之后的下一个元素
if (nw == INF) { // 已遍历完当前轮次,从头开始
nw = 0;
// 重新选择下一轮的起始集合
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw); // 输出并从集合中删除
s1.erase(nw);
p = !p; // 切换到另一个集合
} else { // 处理s2(逻辑同上)
nw = *s2.upper_bound(nw);
if (nw == INF) {
nw = 0;
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw);
s2.erase(nw);
p = !p;
}
}
puts(""); // 处理最后一个果篮的换行
// 输出剩余集合中的元素(每行一个)
while (s1.size() > 1) {
printf("%d\n", *s1.begin());
s1.erase(*s1.begin());
}
while (s2.size() > 1) {
printf("%d\n", *s2.begin());
s2.erase(*s2.begin());
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。