P11231 二叉堆做法

doujiamu · 2024-10-27 16:32:26 · 题解

P11231 二叉堆做法

题目链接
前置知识

分析

考虑贪心，所有被攻击的卡与攻击的卡均构成单调增的序列，给出证明。
题目要求：

• 每张卡牌只能攻击属性比自己小的卡
• 最后剩下的卡要求尽可能小

所以我们要保证以下两点

• 一张卡能被攻击当且仅当它无法攻击任何卡
• 一张卡能攻击另一张卡当且仅当它无法攻击比这张更小的卡

所以被攻击的卡与攻击的卡均构成单调增的序列

排序方法有很多种，我认为二叉堆（优先队列）应该有更高的编写效率和可读性。

时间复杂度 O(n\log{n}) 足以通过本题

参考AC代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, ans;
const int maxn = 1e5 + 7;
priority_queue<int, vector<int>, greater<int>> q, b; //小根堆

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);

    cin >> n;

    for(int x, i = 1; i <= n; ++i){
        cin >> x;
        q.push(x);
    }

    b = q;
    ans = n;
    while(!q.empty()){
        int cmp_p = q.top();
        while(!b.empty()){
            if(b.top()>cmp_p){
                b.pop();
                ans--;
                break;
            }
            b.pop();
        }
        q.pop();
    }

    cout << ans;

    return 0;
}

参考二叉堆实现

#include<bits/stdc++.h>
using namespace std;
int w[1000007],op,z,n;
int tot;

void modify(int x){
    if(x==1||w[x]>w[x/2]){return ;}
    swap(w[x],w[x/2]);
    modify(x/2);
}

void push(int x){
    w[++tot]=x;
    modify(tot);
}
int top(){return w[1];}

void repair(int x){
    if(x*2>tot)return;
    int tar=x*2;
    if(x*2+1<=tot){
        tar=w[x*2]<w[x*2+1]?x*2:x*2+1;
    }
    if(w[tar]<w[x]){
        swap(w[tar],w[x]);
        repair(tar);
    }
}

void pop(){
    swap(w[1],w[tot--]);
    repair(1);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&z);
            push(z);
        }
        else if(op==2){
//          for(int i=1;i<=tot;++i)printf("%d  ]\n",w[i]);
            printf("%d\n",top());
        }
        else{
            pop();
        }
    }

    return 0;
}