ptaR7-5打探基priority

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

输出样例:

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

代码长度限制

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;}elseres=0;//如果不够3个那么不减if (res >= t)cout << "KO";//扣的大于剩下的，输出koelsecout << 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);//如果是负数那么取0pq1.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那么输出KOelse cout<<hp;//如果大于0那么输出血量
}