C++实现UVa 100题出现Time limit exceeded超时问题求助

你的代码超时由三个核心问题导致，按优先级排序：

• 核心逻辑错误引发死循环：你完全写反了奇偶判断的处理逻辑，且把乘号错写为取模符：
  1. 原题规则为：奇数执行3n+1，偶数执行n/2，你的代码里把偶数判定对应了奇数的操作，且把3*n错写为3%n，会导致大量数值进入死循环永远无法到1，这是超时的最主要原因
  2. 代码里的注释也完全写反了奇偶判定的描述，进一步加剧了逻辑错误
• 无缓存重复计算：区间内每个数字的3n+1序列长度都从头计算，大量公共子序列被重复计算，时间复杂度极高
• 输入输出效率不足：cin/cout默认开启和stdio的同步，大输入量下运行效率极低

1. 修正核心逻辑 #

把内层循环的奇偶处理部分替换为正确逻辑：

while (1)
{
    if(n == 1) {
        break;
    } else if (n % 2 == 1) // 奇数处理
    {
        n = 3 * n + 1;
    } else { // 偶数处理
        n = n / 2;
    }
    counter++;
}

2. 增加记忆化缓存 #

开全局数组存储已经计算过的数值的序列长度，避免重复计算：

const int MAX = 1e6 + 10;
int dp[MAX];

int get_len(int n) {
    if(n == 1) return 1;
    if(n < MAX && dp[n]) return dp[n];
    int res;
    if(n % 2 == 1) res = get_len(3 * n + 1) + 1;
    else res = get_len(n / 2) + 1;
    if(n < MAX) dp[n] = res;
    return res;
}

之后遍历区间时直接调用get_len(i)获取长度即可。

3. 优化输入输出 #

在main函数开头加入以下代码，关掉cin/cout同步提升效率：

ios::sync_with_stdio(false);
cin.tie(nullptr);

• 提交前先测试多组边界数据，确认没有逻辑错误引发的死循环
• 涉及重复子问题的计算优先用记忆化、预处理打表的方式降低时间复杂度
• 输入输出量较大的题目，优先使用低开销的IO操作，避免因IO速度不足超时
• 提交前估算算法时间复杂度，确认符合题目时间限制要求

内容的提问来源于stack exchange，提问作者Halima Tora