题目链接
题目大意:
给你n个数(n个宇航员对应的能量值) 一个h ,h表示机器人当前的能量值。机器人拥有2中绿色的药剂,一瓶蓝色的药剂。其中绿色的药剂可以使机器人的能量值变为现在的2倍(2->2 * 2 = 4),蓝色的药剂可以使机器人的能量值变为现在的3倍(2 -> 2 * 3 = 6)。机器人每秒可以进行下列中的任意一个操作:
- 吸收一个拥有更少人类力量的宇航员(即:a[i] < h ),此时h = h + (a[i] / 2), "/"表示整数运算,向下取整。
- 使用绿色药剂(确保他有)
- 使用蓝色药剂(确保他有)
问该机器人最多可以吸收几个宇航员的能量值?
解题思路:
机器人要想吸收更多的人,那么他一定会先吸收,直到不能吸收为止,然后使用药剂。但是药剂有3瓶2种,我们该如何去进行选择呢?(哈哈)仔细想想他不就三瓶吗?我直接枚举不就好了,也不过3种可能,最后求最大值就好了。根据贪心原则,他想要吸收更多人的能量,他就要先吸收能量最小的人。这样也可以用一个优先队列维护,当然排序也是可以的。注意:要使用long long,不然会爆int的。
AC代码:
#include<bits/stdc++.h>
#define int long long
#define sz(a) ((int) (a).size())
#define vi vector< int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10;
int n, h;
int f[3][3] = {{2, 2, 3}, {2, 3, 2}, {3, 2, 2}}; //枚举方案
int a[N];
void solved()
{
cin >> n >> h;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
int cnt, mx = 0, res;
for (int u = 0; u < 3; u ++ )
{
int hh = h;
cnt = 0;
res = 0;
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 1; i <= n; i ++ ) q.push(a[i]);
while (q.size())
{
int hhh = q.top();
q.pop();
if (hhh < hh) //如果可以吸收直接吸收就好了
{
hh += (hhh / 2);
res ++;
continue ;
}
while (hhh >= hh && cnt < 3) //不能直接吸收,那就用药剂增强自己
{
hh *= f[u][cnt++];
}
if (hhh >= hh) break; //增强后也不可以,那就不能吸收了呗
hh += (hhh / 2);
res ++;
}
mx = max(mx, res);
}
cout << mx << '\n';
}
signed main(){
ios :: sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t -- )
{
solved();
}
return 0;
}
/* stuff you should look for 你应该寻找的东西
* int overflow, array bounds (int)溢出,数组边界
* special cases (n=1?) 特殊情况(n=1?)
* do smth instead of nothing and stay organized 做一些事情而不是什么也不做,保证效率
* WRITE STUFF DOWN 将东西写下
* DON'T GET STUCK ON ONE APPROACH 不要在一个地方死磕
*/