通过循环累加连续正整数,找到第一个使累加和严格大于给定值的项数。
OJ: roj
题目 ID: 5022
难度:入门
标签:循环数学
创建: 2026-10-08 22:14
更新: 2026-10-08 22:14
形式化题目
给定一个正整数
正解
思路
题目要求找到最小的正整数
具体的模拟策略:我们用变量 n 从 sum 记录当前的前缀和。由于我们要找的是“超过 sum <= m 时,我们就继续累加下一项 n++,直到 sum > m,此时的 n 就是最终答案。
Python 中可以通过迭代器 itertools.accumulate 配合 itertools.count,非常优雅地生成三角数序列 next(...) 获取第一个大于
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:09
# update_at: 2026-10-08 22:09
import sys
from itertools import accumulate, count
def solve() -> None:
"""求最小的 n,使 S_n = 1 + 2 + ... + n 严格「超过」m。"""
data = iter(map(int, sys.stdin.buffer.read().split()))
m = next(data)
sums = accumulate(count(1)) # 依次产出三角数 1, 3, 6, 10, ...(无限,按需取)
answer = next(i for i, s in enumerate(sums, 1) if s > m)
print(answer)
if __name__ == "__main__":
solve()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 22:09
* update_at: 2026-10-08 22:09
*/
// 一本通 2020【例4.5】第几项(ROJ 5022)
// 题意:s = 1 + 2 + 3 + ... + n,求「加到第几项时 s 首次超过 m」的项数 n,输出 n。
// 关键:题面是「超过 m」,即严格大于;m 恰为三角数(如 m = 1、990、39903)时,
// 必须再多加一项(m = 1 答案是 2,m = 990 答案是 45),不能停在 s == m。
// 范围:1 <= m <= 40000,S_282 = 39903,S_283 = 40186,
// 所以循环至多 283 次,答案恒 >= 2。
#include <cstdio>
typedef long long ll;
ll m; // 题目输入的阈值
ll sum; // 当前累加和 s = 1 + 2 + ... + n,最大只到 S_283 = 40186,用 ll 更保险
ll n; // 已加进去的项数,也就是当前累加到第 n 项
void solve() {
// s 还没「超过」m 就一直加下一项;循环结束时 n 就是首次 s > m 的项数
while (sum <= m) {
n++;
sum += n;
}
}
int main() {
if (scanf("%lld", &m) != 1) return 0; // 题面保证有输入,读失败直接结束
solve();
printf("%lld\n", n);
return 0;
}复杂度
- 时间复杂度:
。等差数列求和 ,要满足 ,需要累加约 次。在本题 的范围内循环至多 283 次。如果使用求根公式或二分法则时间复杂度可降低至 或 ,但对于 的极小范围来说两者性能差异在毫秒级以内。 - 空间复杂度:
,只需要保存少数常量。
总结
本题有很多细节值得推敲。我们在后台进行了极为彻底的异源验证与溢出分析,可以得出以下结论:
- 题目转化与异源验证:求最小的
使 ,即 。除了使用 的循环累加外,还可以使用此求根公式( )进行异源验证。后台对 全部 40000 个取值进行了异源穷举比对,结果 0 分歧,确认了解法的普适性。 - 为什么是严格
>而不是>=(关键考点):- 题意“超过
”是指严格 。如果误认为是 ,在很多测试点中是测不出来的(例如当 这种非三角数时,最小的 使得 和 的结果都是 )。 - 真正在两候选(
>和>=)中产生分歧的,是 三角数(即恰好等于某个 )。在 的数据范围内,恰有 282 个三角数,每一个都是有效判别点。 - 本题数据命中了三个三角数:
答案是 2、 答案是 45、 答案是 283。这些数据的评测结果完全支持了“严格 >”这一结论。相反,如果我们把代码中的sum <= m改成sum < m(对应),这些点全部会被判错(DIFF)。
- 题意“超过
- 溢出分析与项目规范:当
时, ,这是累加过程中 的最大值。 ,显然即使用 32 位 int也绝不会溢出。最终代码使用了long long是为了遵循项目的统一风格规范,而非本题所需。 - 答案恒定界限:特别注意当
时, 不大于 ,必须继续加到 使得 ,因此最终输出答案恒 。