[数据结构与算法]CF1657D：D. For Gamers. By Gamers.（dp，调和级数，二分）

传送门

题意：

• 有 m 场战斗，每场战斗前在 n 种单位中选择一种，使得用拥有的钱招募士兵能打败怪物，同时尽可能少地花费金钱。
• 判定打败怪物的公式是：$\sum (hi)/Di>Hi/\sum (di)$，即士兵攻击的秒伤 严格大于 怪物攻击的秒伤，士兵死完前必定先杀死怪物。这个公式显然可以移一下项 变成 $\sum (hi?di)>Hi?Di$，右边这个东西对于每个怪物是固定的我们定义成 HD。
• 推完公式后就可以开摆了 ，我们从一个全新的角度去维护，定义 cost[i] 为花费 i 金钱能获取的最大攻击力（也就是$\sum (hi?di)$），如果某个 cost[i] 严格大于了 HD，就代表 i 花费能战胜这个怪物，是一个可行解。
• 花费的范围达到了 1e6，该怎么维护？答案用数学中的调和级数维护我们的 cost ：

	forr(i, 1, n) {
		ll a, b, d;
		cin >> a >> b >> d;
		c[a] = max(c[a], b * d);
		//招募一个这种单位，对应的 c[i] 维护一个最大攻击力
	}
 	
 	//调和级数，虽然是双层但遍历的数量很少
	for (int i = 1; i <= m; i++)
		for (int j = 1; i * j <= m; j++) 
			cost[i * j] = max(cost[i * j], c[i] * j);
			//旧花费可以从之前的 一个单位 * 个数 转移到新的花费，还是维护最大攻击力
			
	forr(i, 1, m)cost[i] = max(cost[i], cost[i - 1]);
	//大的花费显然可以从小的花费转移最大攻击力过来

• 可以发现我们的 cost 数组是单调递增的，所以可以结合二分优化搜索的过程。只需要搜索第一个攻击力严格大于 HD 的位置即可，此位置的花费必定最小，如果找不到代表杀不死。

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
#define all(a) a.begin(),a.end()
#define oper(a) (operator<(const a& ee)const)
#define endl "\n"
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

double DNF = 1e17;
const int N = 200010, M = 1000010, MM = 110;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m, k, T, S, D, K;
ll cost[M], c[M];

void solve() {
	cin >> n >> m;
	forr(i, 1, n) {
		ll a, b, d;
		cin >> a >> b >> d;
		c[a] = max(c[a], b * d);
	}

	for (int i = 1; i <= m; i++)
		for (int j = 1; i * j <= m; j++) 
			cost[i * j] = max(cost[i * j], c[i] * j);
	forr(i, 1, m)cost[i] = max(cost[i], cost[i - 1]);

	cin >> k;
	forr(i, 1, k) {
		ll a, b, mos;
		cin >> a >> b;

		mos = a * b;
		int t = upper_bound(cost + 1, cost + 1 + m, mos) - cost;

		if (t == m + 1)cout << -1;
		else cout << t;
		cout << ' ';
	}
}

int main() {
	cinios;
	T = 1;
	while (T--)solve();
	return 0;
}
/*
*/

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖