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 不要在一個地方死磕
 */