题解：AT_abc388_e [ABC388E] Simultaneous Kagamimochi

· · 题解

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

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

那本题我们也可以这样。不妨开两个优先队列，一个 q1 存放已选方案，一个 q2 存放未选用的数，请注意 q1 存放的是一个二元组，以较大数为关键字从小到大排序。

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

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

那么完成了。时间复杂度是 O(n\log n)。

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

#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;
}