CF1989D Smithing Skill

传送门

Solution

注意到每把武器只使用一种金属锻造，可以独立计算每种金属锭的贡献。

把问题转换为：有一个数 $x$ 和 $n$ 个操作，每个操作包含两个参数 $a_i$、$b_i$。当满足 $x\le a_i$，则可执行操作 $i$，使 $x$ 变为 $x-(a_i-b_i)$。求可对 $x$ 操作次数的最大值。

不妨设 $x_i=a_i-b_i$，$y_i=a_i$。使用 map 筛选这些操作并排序，使其构成具有单调关系的排列，满足 $x_i$ 严格递增且 $y_i$ 严格递减，否则将会出现无用的操作。设 $m_x$ 表示筛选出的操作中 $x_i$ 的最大值。

设 $cut_i$ 表示当 $x=i$ 时，进行一次操作后，$x$ 最小的减少值。同时遍历操作和 $[1,m_x]$，可线性求出此区间内的所有 $cut_i$。

设 $sum_x$ 表示当 $x \in [1,m_x]$ 时，可对 $x$ 操作次数的最大值。有递推公式

$sum_i=sum_{i-cut_i}+1$

若 $x>m_x$，则先对 $x$ 进行若干次 $x_i$ 最小的操作，使其小于 $m_x$。这部分的操作次数可 $\Theta(1)$ 得出。然后再加上对应的 $sum_i$ 值即可。

时间复杂度为 $\Theta(n+m+m_x)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

ll n, m, a[N], b[N], cut[N], cnt, maxx, num, sum[N], ans;
map<ll, ll> mp;
struct Node {
	ll x, y;
} c[N];

int main()
{
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) 
		scanf("%lld", &a[i]);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &b[i]);
		if (!mp[a[i] - b[i]])
			mp[a[i] - b[i]] = a[i];
		else mp[a[i] - b[i]] = mp[a[i] - b[i]] < a[i] ? mp[a[i] - b[i]] : a[i];
	}
	c[0].y = 1e9 + 10;
	for (auto &t : mp) {
		if (t.second >= c[cnt].y) continue;
		c[++cnt].x = t.first;
		c[cnt].y = t.second;
		maxx = max(maxx, c[cnt].y);
	}
	int p = 1;
	for (int i = maxx; i; i--) {
		while (p <= cnt && c[p].y > i) ++p;
		if (p > cnt) break;
		cut[i] = c[p].x;
	}
	for (int i = 1; i <= maxx; i++) 
		if (cut[i])
			sum[i] = sum[i - cut[i]] + 2;
	while (m--) {
		scanf("%lld", &num);
		if (num <= maxx)
			ans += sum[num];
		else {
			ans += (num - maxx) / c[1].x * 2;
			if ((num - maxx) % c[1].x)
				ans += 2 + sum[maxx + (num - maxx) % c[1].x - c[1].x];
			else 
				ans += sum[maxx];
		}
	}
	printf("%lld", ans);
	return 0;
}