枚举:优化范围

10 分钟

枚举就是把所有可能一个个试。能不能不超时,往往取决于范围定得准不准——范围缩小一半,时间就省一半。

以"找两个正整数之和为 "为例,第一个数 没必要枚举到 。因为两数为正且不重复地取 ,所以 最大只到 ,超过就重复了:

for (int a = 1; a <= n / 2; a++) {
    int b = n - a;             // 第二个数直接算出来
    // 处理 (a, b)
}

这里还顺手用了个技巧:定了 就唯一确定,根本不用第二层循环。

优化范围的通用思路:先想清楚每个变量的取值必须满足什么条件(正数、有上界、不重复),把这些写进循环的起止和步长。 看着只差常数,但在大数据和多重循环里,常数叠起来就是超时和通过的区别。读题时一定要挖出这些隐含范围。

小纸条

找两个数之和为 n,第一个数最大枚举到多少?

登录 后可看答案

枚举:优化范围 · 考级冲刺 · op599 课程