CF1989D

Xycxxx · 2026-05-12 10:57:29 · 题解

容易想到贪心策略，设当前材料有 c 个，每次选 a_i \le c 且 a_i-b_i 最小的去弄，设 f_c 表示 \min\limits_{a_i\le c} \{a_i-b_i\}。此时直接模拟是 \mathcal{O}(nm) 的。

考虑预处理出 g_c 表示当前材料有 c 个时对答案的最大贡献。有 g_c=g_{c-f_c}+1。

因为 a_i\le 10^6，考虑对于每个材料 c 先 \mathcal{O}(1) 将其减为 \le 10^6，然后直接用 g_c 查询即可。复杂度 \mathcal{O}(n+m)。

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 1e6 + 5;
int n, m, a[N], ans, f[N], g[N], mx;
signed main() {
    n = rd, m = rd; memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) a[i] = rd, mx = max(mx, a[i]);
    for (int i = 1, b; i <= n; ++i) b = rd, f[a[i]] = min(f[a[i]], a[i] - b);
    for (int i = 1; i <= mx; ++i) f[i] = min(f[i], f[i - 1]);
    for (int i = 1; i <= mx; ++i) if (i >= f[i]) g[i] = g[i - f[i]] + 1;
    for (int i = 1, c; i <= m; ++i) {
        c = rd;
        if (c > mx) {
            int t = (c - mx) / f[mx] + 1;
            c -= f[mx] * t;
            ans += t;
        }
        ans += g[c];
    }
    cout << ans * 2;
    return 0;
}