Codechef九月挑战赛MNDIGSM2题本地运行正常提交报运行时错误求助

• 边界条件处理错误：当输入的r < 2时，你计算得到的arSize = (r-2)+1会小于等于0，给vector传入负的大小参数会直接触发内存分配错误；此外当arr为空时调用minVal函数访问arr[0]，会发生数组越界。
• 大输入下内存溢出：该题的测试用例中r的上限极高，当r达到1e5及以上时，你声明的长度为r-1的vector会直接耗尽可用内存，触发内存溢出导致运行时错误，且遍历2到r的循环时间复杂度为O(r)，大r下即使不爆内存也会超时。
• 潜在越界风险：converter函数未处理n=0的输入场景，如果测试用例包含n=0，会跳过循环直接返回sum=0，虽然不会直接崩溃但可能引发后续逻辑异常。

修复建议 #

你不需要遍历所有2到r的基数来求最小数位和：

1. 首先判断如果r >= n，直接返回n即可，此时n在基数n下的表示是10，数位和为1，已经是理论最小值。
2. 当r < n时，只需要枚举到√n的基数即可，同时计算对应的商作为候选基数，时间复杂度可以降到O(√n)，不需要开大容量vector存储所有结果，边遍历边记录最优解即可。

// 优化后的核心逻辑示例
int main() {
    int test;
    cin >> test;
    while(test--) {
        int n, r;
        cin >> n >> r;
        if(r >= n) {
            cout << n << endl;
            continue;
        }
        int min_sum = n;
        int best_base = 2;
        // 仅枚举到sqrt(n)的基数
        for(int b = 2; b * b <= n && b <= r; b++) {
            int sum = 0;
            int tmp = n;
            while(tmp) {
                sum += tmp % b;
                tmp /= b;
            }
            if(sum < min_sum) {
                min_sum = sum;
                best_base = b;
            }
        }
        // 检查大于sqrt(n)的候选基数（对应仅两位的数位表示）
        int k = min(r, n-1);
        while(k*k > n) {
            int sum = (n/k) + (n%k);
            if(sum < min_sum) {
                min_sum = sum;
                best_base = k;
            }
            k = n/(n/k + 1);
        }
        cout << best_base << endl;
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者78_Harsh Prasad