题意分析

题目给定两个整数 K 和 M，要求在 1 到 N（N 需确定）的整数集合里，将所有数字按字典序排序后，K 正好排在第 M 位，需找出满足条件的最小 N；若不存在这样的 N，则输出 0。其中 K 和 M 的范围是 1 到 10 亿，需要考虑高效算法处理。

解题思路

前缀计数：字典序排序和数字前缀有关，先定义函数，统计 1 到 N 范围内，字典序小于等于 K 的数字个数，即 K 在字典序中的位置。计算时将 K 转成字符串，依次枚举其所有前缀，统计每个前缀对应数字的数量。

二分查找：K 是 N 的下界，上界设为较大数，通过二分查找在这个范围内找 N。每次取中间值 mid，用前缀计数函数判断 K 在 1 到 mid 字典序中的位置，若位置等于 M，尝试找更小的 N；若小于 M，说明 N 小了，增大下界；若大于 M，说明 N 大了，减小上界 。 结果输出：

代码

二分查找结束后，若没找到合适的 N，输出 0；找到则输出最小的 N。

#include <string>
using namespace std;

typedef long long LL;

// 将字符串转换为LL类型，替代stoll
LL strToLL(const string& s) {
    LL res = 0;
    for (size_t i = 0; i < s.length(); ++i) {
        res = res * 10 + (s[i] - '0');
    }
    return res;
}

// 将LL类型转换为字符串，替代to_string
string llToString(LL num) {
    if (num == 0) return "0";
    string res;
    bool isNegative = num < 0;
    if (isNegative) num = -num;
    while (num > 0) {
        res = char(num % 10 + '0') + res;
        num /= 10;
    }
    if (isNegative) res = '-' + res;
    return res;
}

LL count_lex(LL N, const string& K_str) {
    LL res = 0;
    int len = K_str.length();
    string prefix;
    for (int i = 1; i <= len; ++i) {
        prefix = K_str.substr(0, i);
        LL p = strToLL(prefix);
        if (p > N) continue;
        LL power = 1;
        for (int j = 0; j < len - i; ++j) power *= 10;
        res += (p == strToLL(K_str.substr(0, i)) ? 1 : 0) * power;
    }
    return res;
}

LL find_min_N(LL K, LL M) {
    string K_str = llToString(K);
    LL low = K, high = 1e18;
    LL res = 0;
    while (low <= high) {
        LL mid = (low + high) / 2;
        LL c = count_lex(mid, K_str);
        if (c == M) {
            res = mid;
            high = mid - 1;
        } else if (c < M) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

int main() {
    LL K, M;
    cin >> K >> M;
    LL N = find_min_N(K, M);
    cout << N << endl;
    return 0;
}