AcWing 4089. 小熊的果篮
原题链接
困难
作者:
duanrui
,
2024-04-10 00:01:26
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
// 删除和查询都是logn,且自带有序
set<int> apple,orange;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
if(x) apple.insert(i);
else orange.insert(i);
}
// 一轮循环就是一个篮子的输出
while (!apple.empty() && !orange.empty()){
auto i = apple.begin();
auto j = orange.begin();
// 让 i j 交替向后,直到一个遍历完成,另一个还剩最后一块
while(i!=apple.end() && j!=orange.end()){
if(*i<*j){
cout<<*i<<' ';
apple.erase(i++);
i=apple.upper_bound(*j);
}
else{
cout<<*j<<' ';
orange.erase(j++);
j=orange.upper_bound(*i);
}
}
// 输出剩的一块
if(i!=apple.end()){
cout<<*i<<' ';
apple.erase(i);
}
if(j!=orange.end()){
cout<<*j<<' ';
orange.erase(j);
}
cout<<endl;
}
// 两个水果集合交替取,剩余的水果一定是同一块,而且编号保证升序,正好每次取的就是最左边的装篮子
for(auto i=apple.begin();i!=apple.end();i++) cout<<*i<<endl;
for(auto j=orange.begin();j!=orange.end();j++) cout<<*j<<endl;
}