ptaR7-5打探基priority_queue的使用

题目

最近乐乐开发出了一款新的游戏《打探基》，这款游戏需要多人配合来玩，至少三个游戏玩家同时出招才能使探基的血量下降一点，同时，出招的每个人战斗力下降一点，当战斗力小于10的时候将不能再出招，不知道多个游戏玩家是否能打败探基。特别声明：探基是游戏中的人物,，请勿前去某宿舍实战。

输入格式:

第一行输入两个整数hp, n(0<hp, n<100000)，ph表示探基初始血量，n表示游戏玩家数量。
第二行输入n个整数，表示n个玩家的初始战斗力。初始战斗力取值范围是[1,100000]。

输出格式:

当游戏玩家有可能打败探基时，输出KO，否则，输出探基最少剩余的血量。

输入样例:

在这里给出一组输入。例如：

100 5
50 30 80 60 60

输出样例:

在这里给出相应的输出。例如：

22

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

思路

本题有两种思路：

1.使用数学的思路，本题思维模拟性较大，代码也比较晦涩难懂，如果理解不了可以参照思路2。

2.使用stl的数据结构priority_queue来进行不断的更新和获得，运用大顶堆的特性来不断进行，更新和替换，具体的代码如下。

priority_queue

先对优先队列有一个简单的认识，默认为大顶堆，构造为priority_queue<int>pq;

?

大顶堆?

大顶堆就是队列头部固定为最大的一个。

小顶堆

小顶堆就是队列头部固定为最小的一个。

代码实现

思路1

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int t;
int res;
int main()
{
    cin >> t >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] -= 9;
        a[i] = max(a[i], 0);
    }
    if (n >= 3)
    {
        for (int i = 1; i <= 3; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (a[i] < a[j])
                    swap(a[i], a[j]);
            }
        }//找最大的三个数

        int x = 0;
        for (int i = 4; i <= n; i++)
            x += a[i];//将后面的所有加和
        //引入只要有三个就一定能打完最小的理念，这里需要深刻理解
        if (x >= (a[1] - a[2]) + (a[1] - a[3]))
        //如果后面所有的大于等于最大的数减第二第三个数的和(最优情况同时避免第二第三个数相等的情况)那么说明这a[1]打完之后还会存留更多，所以加和除以三，寻找能满足的最大值
            res = (a[1] + a[2] + a[3] + x) / 3;
        else if (x >= a[2] - a[3])
        //如果前面条件不满足而满足大于第二个减第三个的值，说明最大的一定打不完，但第二个有可能打完并且更多，所以取a[2]和剩下的加和除以2判断能成立的最大值
            res = (a[2] + a[3] + x) / 2;
        else
        //如果都不满足，那么就是后面能打多少打多少，第二个的值超出了后面的和，一定能打完
            res = a[3] + x;
    }
    else
        res=0;//如果不够3个那么不减
    if (res >= t)
        cout << "KO";//扣的大于剩下的，输出ko
    else
        cout << t - res;//够了还剩，输出剩下的
}

思路2

#include <bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int>pq1;//构造大顶堆
    int hp,n,t,m;
	cin>>hp>>n;//输入血量，人数
	m=n;
	while(m--){
		cin>>t;
		t-=9;//每个人最多打多少次
		t=max(t,0);//如果是负数那么取0
		pq1.push(t);//填充大顶堆
	}
	while(n>=3){
		int x1,x2,x3;
		x1=pq1.top(),pq1.pop();
		x2=pq1.top(),pq1.pop();
		x3=pq1.top(),pq1.pop();//取最大的三个数
		if(x1>0&&x2>0&&x3>0){
			x1--,x2--,x3--,hp--;//直到最大的有一个到0，说明已经打不动了(小于三个人)
			pq1.push(x1),pq1.push(x2),pq1.push(x3);//再填充回去
		}
		else break;//打不动就停止
	}
	if(n<3)cout<<hp;//如果小于3个人直接输出
	else if(hp<=0)cout<<"KO";//如果血量小于等于0那么输出KO
	else cout<<hp;//如果大于0那么输出血量
}

总结

本题带我们熟悉了priority_queue容器的使用，联系了大顶堆和小顶堆，以及思维的理念和想法，笔者更加推崇容器的使用，带我们再次领略stl的魅力和便捷，希望大家能够多多使用stl，跟随笔者慢慢成长。

尾声

本题带我们认识和理解了大顶堆，小顶堆，多加练习，多加熟练。如果觉得笔者写的还不错的话，记得留下你的点赞关注和收藏奥~