1759E(方案枚举）

• 2022 年 11 月 19 日
• 笔记
• CF

题目链接

题目大意：

给你n个数（n个宇航员对应的能量值) 一个h ，h表示机器人当前的能量值。机器人拥有2中绿色的药剂，一瓶蓝色的药剂。其中绿色的药剂可以使机器人的能量值变为现在的2倍（2->2 * 2 = 4)，蓝色的药剂可以使机器人的能量值变为现在的3倍（2 -> 2 * 3 = 6）。机器人每秒可以进行下列中的任意一个操作：

1. 吸收一个拥有更少人类力量的宇航员（即：a[i] < h )，此时h = h + (a[i] / 2), “/”表示整数运算，向下取整。
2. 使用绿色药剂（确保他有）
3. 使用蓝色药剂（确保他有）

问该机器人最多可以吸收几个宇航员的能量值？

解题思路：

机器人要想吸收更多的人，那么他一定会先吸收，直到不能吸收为止，然后使用药剂。但是药剂有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 不要在一个地方死磕
 */