98 lines
4.1 KiB
C++
98 lines
4.1 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
using namespace std;
|
|||
|
|
const int N = 2e5 + 10; // 定义数组最大长度
|
|||
|
|
const int INF = 0x3f3f3f3f; // 定义一个很大的数作为哨兵
|
|||
|
|
int n; // 水果的总数
|
|||
|
|
set<int> apple, orange; // 使用两个集合分别存储苹果和橘子的位置
|
|||
|
|
|
|||
|
|
/*
|
|||
|
|
这个代码的主要思路是：
|
|||
|
|
|
|||
|
|
1. 使用set容器来存储水果的位置,而并不是记录的“块”，set的特点是自动排序且支持快速查找
|
|||
|
|
2. 每次都选择当前位置之后最近的目标水果（通过upper_bound实现）
|
|||
|
|
3. 每轮选择时会交替选择不同种类的水果
|
|||
|
|
4. 当一轮无法继续选择时（遇到INF），就开始新的一轮
|
|||
|
|
5. 有苹果有桔子，一替一个处理,在循环中不断变换需要找的水果类别，一个个输出;
|
|||
|
|
如果只有其中一种了，单独处理剩余的水果。
|
|||
|
|
|
|||
|
|
使用set的好处是：
|
|||
|
|
1. 自动维护水果位置的顺序
|
|||
|
|
2. upper_bound操作效率高，可以快速找到下一个合适的水果
|
|||
|
|
3. 删除操作也很高效
|
|||
|
|
4. 使用set要以避开区间合并的问题，代码更简单直接
|
|||
|
|
这种方法比暴力遍历数组的方法效率要高得多。
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
// 现在要挑选哪种
|
|||
|
|
int chooseFruit() {
|
|||
|
|
// 1 代表苹果，0 代表桔子
|
|||
|
|
int flag = 0;
|
|||
|
|
if (*apple.begin() < *orange.begin())
|
|||
|
|
flag = 1; // 如果苹果的最小位置更小，就先选苹果,
|
|||
|
|
// 否则先选橘子
|
|||
|
|
return flag;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
cin >> n;
|
|||
|
|
// 读入每个位置的水果类型并存入对应的集合
|
|||
|
|
for (int i = 1; i <= n; i++) {
|
|||
|
|
int x;
|
|||
|
|
cin >> x;
|
|||
|
|
if (x)
|
|||
|
|
apple.insert(i); // 1表示苹果，将位置i加入苹果集合
|
|||
|
|
else
|
|||
|
|
orange.insert(i); // 0表示橘子，将位置i加入橘子集合
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 在两个集合末尾都插入一个无穷大的值作为哨兵
|
|||
|
|
// 这样可以防止upper_bound查找时越界
|
|||
|
|
apple.insert(INF);
|
|||
|
|
orange.insert(INF);
|
|||
|
|
|
|||
|
|
int cur = 0; // 记录当前处理到的位置
|
|||
|
|
bool flag = chooseFruit(); // 标记当前应该选择哪种水果：0表示苹果，1表示橘子
|
|||
|
|
// 通过比较两种水果的最小位置来决定先选择哪种
|
|||
|
|
// 如果苹果的最小位置更小，就先选苹果,否则先选橘子
|
|||
|
|
|
|||
|
|
// 主循环：只要还有水果可选就继续
|
|||
|
|
// apple.size() > 1 表示除了INF外还有苹果
|
|||
|
|
// orange.size() > 1 表示除了INF外还有橘子
|
|||
|
|
while ((flag && apple.size() > 1) || (!flag && orange.size() > 1)) {
|
|||
|
|
if (flag) { // 选择苹果的情况
|
|||
|
|
cur = *apple.upper_bound(cur); // 找到当前位置后面最近的苹果
|
|||
|
|
if (cur == INF) { // 如果找到的是INF，说明这一轮结束了
|
|||
|
|
cur = 0; // 重置当前位置为0, 重新决定下一轮先选哪种水果
|
|||
|
|
flag = chooseFruit(); // 下一轮是苹果还是桔子开始，需要根据函数决策
|
|||
|
|
puts(""); // 输出换行，表示一轮结束
|
|||
|
|
continue;
|
|||
|
|
}
|
|||
|
|
printf("%d ", cur); // 输出选中的苹果位置
|
|||
|
|
apple.erase(cur); // 从集合中删除已选择的苹果
|
|||
|
|
flag = !flag; // 切换到选择另一种水果
|
|||
|
|
} else { // 选择橘子的情况，逻辑同上
|
|||
|
|
cur = *orange.upper_bound(cur);
|
|||
|
|
if (cur == INF) {
|
|||
|
|
cur = 0;
|
|||
|
|
flag = chooseFruit();
|
|||
|
|
puts("");
|
|||
|
|
continue;
|
|||
|
|
}
|
|||
|
|
printf("%d ", cur);
|
|||
|
|
orange.erase(cur);
|
|||
|
|
flag = !flag;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 处理剩余的水果（如果有的话）
|
|||
|
|
puts(""); // 先输出一个换行
|
|||
|
|
while (apple.size() > 1) { // 处理剩余的苹果
|
|||
|
|
printf("%d\n", *apple.begin());
|
|||
|
|
apple.erase(apple.begin());
|
|||
|
|
}
|
|||
|
|
while (orange.size() > 1) { // 处理剩余的橘子
|
|||
|
|
printf("%d\n", *orange.begin());
|
|||
|
|
orange.erase(orange.begin());
|
|||
|
|
}
|
|||
|
|
return 0;
|
|||
|
|
}
|