找零钱

背景

  在某天下午cbl叫我看一个题，[C. 找零问题（再次加强版）](C. 找零问题（再次加强版） - 2022小学期——Day03 - 比赛 - XJTUOJ (xjtuicpc.com))，浅浅写了一下，不出意外的WA了。随后凯爹的代码就来了，我看了一下，没怎么看懂，我又觉得我的思路没问题，于是我就开启了自己造数据，用凯爹的代码来找自己代码的问题，最后找出来了。但是经历了前一天晚上那场痛苦的cf，于是乎我暴躁起来了，看着凯爹空间复杂度$O(n+x)$,我就开启了自己出题之旅……

思路

  对于类似的找钱的问题，第一眼看上去要么是贪心，要么是dp，不出意外，本题有贪心的思想。

  首先，对于组成区间$[1,x]$中所有数字，我们可以知道$1 \in a$,于是有了不成立的条件$1 \notin a$.当$1 \in a$时，区间$[1,x]$中所有数字都可以被组成，只是个数问题。

  对于用数组$a$中的元素组成$x$，且数量最少我们自然而然想到贪心，即先选数值大的钱币。所以首先的需要对数组$a$进行排序。然后，我们假设$a$中只有两个元素$\{1,a_2\}\ (1 \leq a_2)$,则钱币个数：

$$res=x/a_2+x\%a_2$$

假设$x$恰好等于$2*a_2-1$时，此时所需的纸币数量最少为$a_2$张($a_2-1$张面值为$1$和$1$张面值为$a_2$)，此时，$[1,2*a_2-1]$中的数字都可以被组成。

  对于$n \geq 3$的情况，设$a=\{1,a_2,\dots,a_n\},(1 \leq a_2 \leq \dots \leq a_n)$,$sum$为手中钱币面值和,若$sum \geq a_i-1$,，我们可以得到$[1,x]$中的数都可以被组成，此时：

$$x=sum+k*a_i \quad (k \in N,N为自然数)$$

为了使$x$最大时纸币数量最少，我们尽可能选取面值最大的纸币，需要补足的钱币张数为：

$$y=(a_i-1-sum-1)/a_{i-1}+1 \quad (sum < a_i-1)\\ sum+=a_{i-1}*y \\sum+=a_i \quad (sum=a_i-1)$$

再将钱币数量加上即可得到最终答案。

第一个减一为$sum$到$a_i-1$的差值，再进行向上取整的除法

if (t<a[i]-1)
{
    y = (a[i] - t - 2) / a[i - 1] + 1;
    res += y;
    t += y * a[i - 1];
}
if (t<a[i])
{
    res++;
    t += a[i];
}

直到纸币大小枚举完或者$a_i > x$时停止，对剩下的值贪心补差值:

if (t<x)
{
    y = (x - t - 1) / a[i - 1] + 1;
    res += y;
}

完整代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define WA return 0;
using namespace std;

inline ll read() { ll x = 0, z = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-')z = -1; c = getchar(); }while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }return z * x; }
inline void writ(ll x) { if (x < 0) { putchar('-'); x = (~x) + 1; }if (x > 9)writ(x / 10); putchar(x - x / 10 * 10 + 48); }

const int N=1e6+5;
ll n, x;
ll a[N] = { 0 };
ll res = 1;								//res为钱币数量

void Qingtuan() {
    n = read(); x = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    sort(a + 1, a + n + 1);
    if (a[1] != 1)
    {
        printf("-1");
        return;
    }
    int i; ll t = 1; ll y;			//t为此时手中钱币价值和
    for (i = 2; i <= n; i++)
    {
        if (t >= x||a[i]>x)
        {
            break;
        }
        if (a[i] <= t)
        {
            continue;
        }
        if (t<a[i]-1)
        {
            y = (a[i] - t - 2) / a[i - 1] + 1;
            res += y;
            t += y * a[i - 1];
        }
        if (t<a[i])						//此时t==a[i]-1
        {
            res++;
            t += a[i];
        }
    }
    if (t<x)
    {
        y = (x - t - 1) / a[i - 1] + 1;
        res += y;
    }

    writ(res);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen("data.in","r",stdin);
    //int T=read();while (T--)
    Qingtuan();
    //fclose(stdin);
    WA
}