Educational Codeforces Round 125 D. For Gamers. By Gamers.

传送门

题目大意

有 \(n(1\leq n\leq 3\times 10^5)\) 种单位，\(C(1\leq C\leq 10^6)\) 个金币，只能选择一种单位进行招募，在总花费不超过 \(C\) 的情况下，可以招募若干个，每种单位 \(i\) 有单价 \(c_{i}(1\leq c_{i}\leq C)\) ， 攻击力 \(d_{i}\) ， 生命值 \(h_{i}(1\leq d_{i},h_{i}\leq 10^6)\) 。需要击败 \(m\) 个怪物，每个怪物 \(j\) 有攻击力 \(D_{j}(1\leq D_{j}\leq 10^6)\)， 生命值 \(H_{j}(1\leq H_{j}\leq10^{12})\) 。对于每种怪物，需要击杀其后所有招募的单位都要存活，也就是要求击杀怪物的时间小于怪物击杀一个所招募单位的时间，击杀的时间就是生命值/总的攻击力，对于每种怪物，求满足要求的最小花费，如果不能满足，输出 \(-1\) 。

思路

对于招募了 \(k\) 个第 \(i\) 种单位， 第 \(j\) 种怪物，满足要求的条件为 \(\frac{H{j}}{kd_{i}}<\frac{h_{i}}{D_{j}}\) ，也就是 \(kd_{i}h_{i}>D_{j}H_{j}\) 。因为只能招募一个种单位，于是我们可以预处理出 \(B[\space]\) 为每个价格 \(kc_{i}\) 下，能够获得的最大 \(kd_{i}h_{i}\) 。之后令 \(b[i]=max(b[i],b[i-1])\) ，即可这样数组 \(b\) 便是升序的，之后我们二分找到最小的满足要求的 \(c\) 即可。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 1000010;

LL N, C, M;
LL A[maxn], B[maxn], c[maxn], d[maxn], h[maxn], D[maxn], H[maxn];

void solve()
{
	for (int i = 1; i <= N; i++)
		A[c[i]] = max(A[c[i]], d[i] * h[i]);
	for (int i = 1; i <= C; i++)
	{
		if (A[i])
		{
			for (int j = 1; i * j <= C; j++)
				B[i * j] = max(B[i * j], A[i] * j);
		}
	}
	for (int i = 1; i <= C; i++)
		B[i] = max(B[i], B[i - 1]);
	for (int i = 1; i <= M; i++)
	{
		LL J = H[i] * D[i];
		LL ans = upper_bound(B + 1, B + C + 1, J) - B;
		cout << (ans > C ? -1 : ans) << ' ';
	}
	cout << endl;
}

signed main()
{
	IOS;
	cin >> N >> C;
	for (int i = 1; i <= N; i++)
		cin >> c[i] >> d[i] >> h[i];
	cin >> M;
	for (int i = 1; i <= M; i++)
		cin >> D[i] >> H[i];
	solve();

	return 0;
}