[CSP-J 2021] 小熊的果篮 题解

题目链接

既然只有两种东西，我们不妨分开考虑，这里也借鉴了很多二分图题目的切入点。

假设苹果和桔子下标分别如下图所示：

苹果：1 3 6 7 9 10 
桔子：2 4 5 8 

那么第一次取，应该是这样取：

1 2 3 4 6 8 9

也就是先取开头比较小的，然后轮流取，注意一定保证递增，也就是对于苹果找出来的 \(x\)，要在桔子里面找出第一个大于 \(x\) 的数字，然后交替操作。

操作到最后，要么苹果和桔子都取完，要么单剩一堆苹果或者一堆桔子，这时逐个输出即可。

那么只需要维护两个 \(set\)，支持快速查找以及快速删除，事件复杂度 \(\rm O(n\log n)\)。

代码：

int n;
set<int> s[2];
set<int>::iterator it;

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x=read(); s[x].insert(i);
	}
	while(s[0].size()&&s[1].size()) {
		if(*s[0].begin()>*s[1].begin()) swap(s[0],s[1]);
		int p=0,t=0;
		while(s[t].size()) {
			it=s[t].lower_bound(p);
			if(it==s[t].end()) break;
			cout<<*it<<" ";
			s[t].erase(it);
			t=!t; p=*it;
		}
		cout<<"\n";
	}
	if(s[0].size()<s[1].size()) swap(s[0],s[1]);
	for(it=s[0].begin();it!=s[0].end();++it) cout<<*it<<"\n";
	return 0;
}