Codeforces 1657D - For Gamers. By Gamers.

2022 年 03 月 28 日

1378 次浏览

950字数

### [1657D - For Gamers. By Gamers.](https://codeforces.com/contest/1657/problem/D "Educational Codeforces Round 125 (Rated for Div. 2)")

## 题意

每种英雄有价格$c$、攻击力$d$和血量$h$。每个怪物有攻击力$d$和血量$h$。攻击被看做连续而非离散动作（只计算DPS而并非回合制攻击）。

你有一些金钱$C$，给出一些英雄和若干怪物，对每个怪物请计算——在每次只能买一种英雄，且不损失任何英雄的情况下，最少花多少钱能打赢它？

每个怪物的情况计算是不相干的。

## 分析

只要有一个英雄去世条件便不满足，所以买多个英雄只能增强攻击力，再根据题意不等式变换一下就知道只要$\frac{C}{c_x}d_xh_x>d_yh_y$即可获胜。

自然想到可以维护“对于每个$d*h$，我们最少需要花费的金钱”。

又因为有

$$
i<j\space\And\space money_i>money_j \space \rightarrow \space money_i:=money_j

那么$dh$可以被递推成单调的。那么对于每一个怪物，做一次二分查找即可。

但问题来了，这样维护$d*h$显然会爆空间。那么定义域和值域做一下**变换**，结果显然**仍然单调**！此时维护的是

$$
i>j\space\And\space dh_i<dh_j \space \rightarrow \space dh_j:=dh_i

所以我们就维护**各个数额的开销可以达到的最大$dh$** 即可。

接下来是第二个问题，英雄可以买多个，那么我们要暴力更新英雄的数量的话，显然会T。接下来就是重点，一个**非常妙的更新方式**：

```cpp
FOR(base,1,C/2)//base表示钱币基数
	for (int t = 1; t*base <= C; t++)//使用1倍，2倍……直到最高数额的金币
		UPDmax(dh[t*base], dh[base]*t);
```

这个更新方式某种意义上算是离线操作。如果每种英雄都要用来**独立**更新整个数列，那么最坏时间复杂度是$O(\frac{C}{c}*n)=O(Cn)$——这显然是不可接受的。但仔细思考可以发现，我们需要更新的并不是每个英雄，而是每个开销$c$下的“$dh$**最大值**”。所以大量会造成大时间开销的英雄是没用的。而这样在整个$c$的取值范围更新，开销就来到了$\sum^{C}_{i=1}\frac{C}{i}=O(C\log C)$！

然后因为这个数列是单调的，对怪物的$d*h$做二分查找得到的下标即为最小开销。

## 代码

```cpp
int n, C, m;
#define N 1000006
ll dh[N];
int main()
{
	cin >> n >> C;
	FOR(i, 1, n)
	{
		ll c, d, h;
		cin >> c >> d >> h;
		UPDmax(dh[c], d * h);
	}
	FOR(base, 1, C / 2)						// base表示钱币基数
		for (int t = 2; t * base <= C; t++) //使用1倍，2倍……直到最高数额的金币
			UPDmax(dh[t * base], dh[base] * t);
	FOR(i, 1, C)
		UPDmax(dh[i], dh[i - 1]);
	cin >> m;
	while (m--)
	{
		ll d, h;
		cin >> d >> h;
		int x = upper_bound(dh + 1, dh + C + 1, d * h) - dh;
		if (x >= C + 1)
			cout << "-1 ";
		else
			cout << x << " ";
	}
	return 0;
}
```

第二个循环为什么要放在第一个循环后面：

因为每个点**只能更新它的倍数**，可能导致某个数被更新后比左右两侧的数大，破坏单调性。所以维护单调性要放在后面进行。