题解：P9789 [ROIR 2020 Day 2] ATM

· · 题解

思路

首先考虑解决前四个子问题，其中 q\le 5。在这种情况下，每个查询都可以独立处理。

在第一个子问题中，b \le 500，n \le 500，所以我们可以想到 dp。 用 dp_i 表示，如果我们要求的金额为 i，将发行的票据数量。那么 dp_0=0，设 m(i) 是不超过 i 的最大面额的纸币，那么 dp_i= dp_{i-m(i)}+1。则答案是 dp_1 \cdots dp_b 中的最大值。该方案时间负责度 O(nb)。

为了将描述的解决方案衍生到第三个子问题，我们可以在时间负责度中去掉 n。要做到这一点，我们可以发现，m(i) 只随着 i 的增加而增加，所以在计算 dp_i 的过程中，我们可以保持 m(i)= a_j 的当前值，当我们移动到 i 的下一个值时，检查我们是否不能移动到下一个面额 a_{j+1}。该方案时间负责度是 O(b+n)。

在第二个子任务中，纸币的面额是 2 的连续次方。注意，为了支付一个金额 c，自动取款机的纸票的面额与 c 的二进制符号中的 1 的位置相对应。因此，问题被简化为找到一个不超过 b 的数字，其中包含二进制符号中的最大单位数。假设 b 的二进制符号包含 k 个数字，那么答案中的单位数不超过 k，而数字 2^{k-1}-1 显然小于 b，并且正好包含 k-1 个二进制单位。所以答案要么是 b，要么是 2^ {k-1}-1，可以得出 O(\log b) 的解决方案。

第四个子问题的解决已经更接近于完整的解决方案: 这个子问题中对 n,a_i 和 b_i 的约束是最大的，只有 q \le 5。我们可以使用 O(n) 的时间负责度来这个子问题。

正确的解决方案是基于一个贪心算法。让我们对该问题进行反转。设 mn_x 为最小数字 c，使自动取款机为总和 c 发放 x 张纸币。我们仍将以 m(v) 表示不超过 v 的纸币的最大面额。我们可以证明 mn_x = mn_{x-1} +m(mn_x)。

一方面，mn_{x-1} \le mn_x -m(mn_x)，因为从产生总和 mn_x 的纸币集合中，我们总是可以删除最大的纸币(等于 m(mn_x))，并得到产生总和 mn_x-m(mn_x) 的 x - 1 张纸币集合的正确结果。

另一方面，假设我们固定 x，并且 mn_{x-1} < mn_x-m(mn_x)。我们可以看到，在这种情况下，数值 mn_{x-1}+m( mn_x)< mn_x，当被要求提供 mn_x 时，自动取款机将正好返回纸币—— 一张 m(mn) 纸币(它是最大的，不超过这个数额)，以及另外 x-1 张纸币，总和等于 mn_{x-1}，所以假设不成立，mn_x = mn_{x-1}+m(mn_x)。

利用这一观察，我们可以在 O(n) 时间负责度内计算出 mn_x 的所有值。

为了解决最后一组问题，我们可以注意到，没有必要对不同的 b_j 进行独立求解，但只要通过二分搜索找到最后的 a < b_j，并查看相应的 mn_x 值的即可。

代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
const int N = 2e5 + 10;
int n, Q, x, a[N], u[N], v[N];
main()
{
    scanf("%lld", &n);
    rep(i, 1, n) scanf("%lld", &a[i]);
    rep(i, 1, n - 1) 
    {
        int t = (a[i + 1] - u[i] - 1) / a[i];
        u[i + 1] = u[i] + t * a[i];
        v[i + 1] = v[i] + t;
    }
    scanf("%lld", &Q);
    for(; Q; -- Q)
    {
        scanf("%lld", &x);
        int t = upper_bound(a + 1, a + n + 1, x) - a - 1, p = (x - u[t]) / a[t];
        printf("%lld %lld\n", u[t] + p * a[t], p + v[t]);
    }
    return 0;
}