1759E(方案枚举）

题目链接

题目大意：

给你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代码：

cpp

#include#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 pairusing 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, greater > 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 不要在一个地方死磕 */

 

• 题目链接
•     题目大意：
•     解题思路：
• AC代码：

__EOF__