CF1862F

洛谷题目链接

Codeforces题目链接

分析

观察到不管怎么打打完所有怪物的总能量是不变的，统计打完所有怪兽的能量和，记为 $sum$。

可以考虑一些怪物用 $i$ 单位的水能量来打败，剩下的用 $sum?i$ 单位的火能量来打败，产生 $i$ 单位的水能量的时间为 $?\frac{i}{w}?$，产生 $i$ 单位的水能量的时间为 $?\frac{sum?i}{f}?$。

但是 $i$ 单位的水能量可能打不完整数只怪兽，所以还得跑一遍背包，判断每个 $i$ 是否可行，但是 dp 数组开 int 类型可能会 MLE 所以得用 bool 类型。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100000005, M = 105;
int T, n, w, f, s[M];
bool dp[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(cin >> T; T; T --){
		memset(dp, 0, sizeof dp);
		int sum = 0;
		cin >> w >> f >> n;
		for(int i = 1; i <= n; i ++){
			cin >> s[i];
			sum += s[i];
		}
		dp[0] = 1;
		for(int i = 1; i <= n; i ++){
			for(int j = sum; j >= s[i]; j --){
				dp[j] |= dp[j - s[i]];
			}
		}
		int minn = 1e9;
		for(int i = 0; i <= sum; i ++){
			if(dp[i]){
				int water = ceil((double)(i) / (double)(w));
				int fire = ceil((double)(sum - i) / (double)(f));
				minn = min(minn, max(water, fire));
			}
		}
		cout << minn << "\n";
	}
	return 0;
}