题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

有点小题大做的感觉，本题我们使用反悔贪心解决。

反悔贪心的一般策略大概可以概括为：能对答案产生贡献的方案就直接选下来，否则，我们找一下前面选过的最不优的方案进行更换。

那本题我们也可以这样。不妨开两个优先队列，一个

q1

存放已选方案，一个

q2

存放未选用的数，请注意

q1

存放的是一个二元组，以较大数为关键字从小到大排序。

先排序。然后往后面扫。设当前扫到的是

now

。

如果 $q2$ 中的最小数 $top$ 可以与之搭配，即满足 $top\times 2\le now$ ，那么搭配，将二元组 $(top,now)$ 存进 $q1$ 。答案加一。
若不能，取出 $q1$ 的队头 $(x,y)$ ，改为 $(x,now)$ 。然后把 $y$ 弹入 $q2$ 。这一步的操作可以理解为，把较小的 $y$ 取出来，以便后面和其他的数配对。
如果上述两种均不满足，那就直接将 $now$ 弹入 $q2$ 。

那么完成了。时间复杂度是

O(n\log n)

。

请注意，由于优先队列存放 pair 时以第一个数为关键字，所以我们把二元组对调即可。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+10;
int a[N],n,ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > q1;
	priority_queue<int,vector<int>,greater<int> > q2;
	for(int i = 1;i<=n;i++){
		if(!q2.empty() && q2.top()*2 <= a[i]){
			ans++;
			q1.push(make_pair(a[i],q2.top()));
			q2.pop();
		}
		else if(!q1.empty() && q1.top().first < a[i]){
			pair<int,int> f = q1.top();
			q1.pop();
			q2.push(f.first);
			q1.push(make_pair(a[i],f.second));
		}
		else q2.push(a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

文章操作

相关推荐

评论

题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi