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;
}