一开始想复杂了，但是总感觉思路也没什么问题，思路是枚举每一个a作为开头，利用getmax函数求出能够在后面拼接的最大数使得<=k，然后在a数组中利用二分找到满足条件的个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 15;
int n;
ll K, A[N], cnt;
int k[M], a[N][M];
void f(ll x, int* arr)
{
    int digit = 0;
    while (x)
    {
        arr[++digit] = x % 10;
        x /= 10;
    }
    reverse(arr + 1, arr + 1 + digit);
    arr[0] = digit;
}
ll getmax(ll x, const int& index)
{
    ll res = 0;
    bool limit = true;
    for (int i = 1; i <= a[i][0]; i++)
    {
        if (a[index][i] < k[i])
        {
            limit = false;
            break;
        }
        else if (a[index][i] > k[i] && limit)
        {
            for (int i = a[index][0] + 1; i < k[0]; i++) res = res * 10 + 9;
            return res;
        }
    }
    if (limit)
    {
        bool pre = false;//前导零
        for (int i = a[index][0] + 1; i <= k[0]; i++)
        {
            if (k[i] == 0)
            {
                if (pre) return 0;//无法实现
                pre = true;
            }
            res = res * 10 + k[i];
        }
    }
    else
    {
        for (int i = a[index][0] + 1; i <= k[0]; i++) res = res * 10 + 9;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> K; f(K, k);
    for (int i = 1; i <= n; i++) cin >> A[i];
    sort(A + 1, A + 1 + n);
    n = upper_bound(A + 1, A + 1 + n, K) - A - 1;
    for (int i = 1; i <= n; i++) f(A[i], a[i]);
    for (int i = 1; i <= n; i++)
    {
        ll res = upper_bound(A + 1, A + 1 + n, getmax(A[i], i)) - A - 1;
        cout << getmax(A[i], i) << ' ' << res << '\n';
        if (res >= i) res--;
        cnt += res;
    }
    cout << cnt;
    return 0;
}

f函数是用来将数分解成一位一位存储方便getmax函数使用