P11231 [CSP-S 2024] 决斗 题解

wwwidk1234 · 2024-10-26 23:10:07 · 题解

2025.1.8 纠正：「建立两个大根堆」有误，应为「建立两个小根堆」

思路：先从 r_i \le 2 入手，容易发现要使剩下的怪兽最少，必须要让每个 r=2 的怪物杀死一个 r=1 的怪物。

试着将结论推广到 r \le 10^5 的情况，只需要让一只怪兽杀死一只防御力和自己攻击力最接近且比自己攻击力小的怪物。比如对于以下怪兽：

可以进行以下操作：

1. 让一只 r=3 的怪兽杀一只 r=1 的怪兽：{\color{red}6,6},{\color{blue}5},{\color{green}4,4},{\color{brown}3},{\color{purple}\xcancel{1}}

2. 让一只 r=4 的怪兽杀一只 r=3 的怪兽：{\color{red}6,6},{\color{blue}5},{\color{green}4,4},{\color{brown}\xcancel{3}},{\color{purple}\xcancel{1}}

3. 让一只 r=5 的怪兽杀一只 r=4 的怪兽：{\color{red}6,6},{\color{blue}5},{\color{green}4,\xcancel{4}},{\color{brown}\xcancel{3}},{\color{purple}\xcancel{1}}

4. 让两只 r=6 的怪兽杀一只 r=4 和一只 r=5 的怪兽：{\color{red}6,6},{\color{blue}\xcancel{5}},{\color{green}\xcancel{4},\xcancel{4}},{\color{brown}\xcancel{3}},{\color{purple}\xcancel{1}}

对于 r=1 的怪兽，只需要让它挠一下 r \ge 1 的怪兽即可。因为敌方防御力大于等于自己攻击力，所以本次攻击无事发生。

我们只需要建立两个小根堆（即优先队列，C++ 中的 priority_queue）维护一个杀手队列和一个猎物队列，将每个 r 加入，当杀手队列非空的时候进行如下操作：

• 如果当前杀手、猎物队列队首元素 k_1,m_1 满足 k_1>m_1，即当前杀手攻击力大于猎物防御力时，说明杀手可以杀死猎物，弹出杀手和猎物队列的首元素。
• 否则，说明杀手杀不死猎物，只需弹出杀手队列的首元素即可。

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

/*
  期望得分:100pts
  算法:贪心
  思路:优先队列,让一只攻击力尽量小的怪兽杀死一只防御力差不多的怪物
  5oiR5piv6YKj57u06I6x54m555qE54uX
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
int a[N];
priority_queue<int,vector<int>,greater<int>> killer,mob;
//杀手和猎物
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) 
    {
        killer.push(a[i]);
        mob.push(a[i]);
    }
    while(!killer.empty())
    {
        int k1=killer.top();killer.pop();
        int m1=mob.top();
        if(k1>m1) mob.pop();
    }
    cout<<mob.size();
    return 0;
}