P4415 数列求和（入门）

解题思路

从1开始一项一项加：1、1+2、1+2+3……问加到第几项时总和第一次超过n。题目点名要求用do while。do while的特点是"先干活、后检查"：不管条件成不成立，循环体都至少执行一次，非常适合"先加一项再判断够不够"的流程。我们准备两个变量：s存累计总和，i存当前加到第几项。循环里先执行 s+=i（把第i项加进去），再 i++（准备加下一项），然后检查 while(s<=n)：只要总和还不大于n，就继续循环。循环结束时，s已经超过了n，而让s超过n的正好是第 i-1 项，所以输出 i-1。边界情况：n最小是2，第1项1不大于2，第2项1+2=3大于2，所以至少要加2项，循环不会出现只加一项就停的情况；n最大1000，加到第45项左右（1+2+…+45≈1035）就超过1000了，循环次数很少。

参考代码

// 程序用途：用do while计算1+2+3+...+i加到第几项时总和会大于n
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int s = 0, i = 1;               // s是当前总和，i是当前项数
    do {
        s += i;                     // 加上第i项
        i++;                        // 准备加下一项
    } while (s <= n);               // 总和还不大于n就继续
    cout << i - 1 << endl;          // 输出让总和超过n的那一项
    return 0;
}

复杂度分析

因为 1+2+…+i ≈ i×(i+1)/2，要让总和超过n，i大约在 √(2n) 这个量级，所以循环次数约 O(√n)。n最大1000，最多几十次循环，非常快。额外空间只用两个变量，是 O(1)。