纸上写了 n 个数字，牛牛在之前改动了几个数字，他忘了他具体改了些数字了。

但是他记得动之前这些数字的和是 的，求他最少改动几个数字。

注意：这些数字在改之前和改之后均在 0 ~ 9 之间，且为整数。

输入描述:

第一行给出 n,m

第二行给出 n 个 0 ~ 9 的整数

输出描述:

输出最少改动了几个数字。(保证答案 )

2 3
1 1

1

备注:

对于  数据有 

对于  数据有 

解题思路

Plan A：最容易想到的一个思路，也是我第一个A的思路，输入，求和，排序，从小开始改成9，改了几个数计数器累计起来。

Code A

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}


const int N = 1e6+7;
int a[N];

int main(){
    int n=read(),m=read(),sum=0;
    for(int i=1;i<=n;++i){
        a[i]=read();
        sum+=a[i];
    }
    if(sum>=m)
        puts("0");
    else{
        sort(a+1,a+1+n);
        int cnt=0;
        for(int i=1;i<=n;++i){
            sum+=9-a[i];
            ++cnt;
            if(sum>=m)    break;
        }
        printf("%d\n",cnt);
    }
    return 0;
} 

// 57MS

Plan B：我发现不需要我们一个个去枚举在排序，只要在输入的时候记着0-9每个数字出现几次，在去按0开始到9全部改还是改一部分，分别计数。掉个log复杂度。

Code B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int a[15];

int main(){
    int n=read(),m=read(),sum=0;
    for(int i=1;i<=n;++i){
        int x=read();
        ++a[x];
        sum+=x;
    }
    if(sum>=m)
        puts("0");
    else{
        int cnt=0;
        for(int i=0;i<10;++i){
            int tmp=sum+a[i]*(9-i);
            if(tmp==m){
                cnt+=a[i];
                break;
            }
            else if(tmp>m){
                cnt+=ceil((1.0*m-sum)/(9-i)); //向上取整
                break;
            }
            else
                cnt+=a[i],sum=tmp;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

// 47MS