P4383 肥宅快乐水（入门）

解题思路

商场开业发快乐水：第 1 个顾客领 2 瓶，第 2 个顾客领 4 瓶，第 3 个顾客领 6 瓶……也就是第 i 个顾客要领 2 × i 瓶。现在一共有 n 瓶水，要输出能发给几个顾客、每个顾客领几瓶。

我们"一个顾客一个顾客地发"：用一个变量 used 记已经发出去的总瓶数，从第 1 个顾客开始。如果剩下的水够发给当前顾客（used + 这人的量 <= n），就发给他并输出"编号 数量"，然后把 used 加上这人的量；如果不够，就停止发放。

拿样例 n=100 验证：第 1 人领 2 瓶；第 2 人领 4 瓶；……第 9 人领 18 瓶，发完一共发出 2+4+6+8+10+12+14+16+18 = 90 瓶；轮到第 10 人要领 20 瓶，90 + 20 = 110 > 100，不够了，停！所以能发给 9 个顾客，和样例一致。

边界情况：如果 n 很小，比如 n=1，第 1 个顾客要领 2 瓶，可是总共只有 1 瓶不够发，于是一个人也发不了，程序什么都不输出。判断"不够就停"要用 if (used + take > n) break，注意是大于就停，等于正好发完时还能继续尝试下一个。

参考代码

// 程序用途：按第i个顾客领2i瓶发快乐水，统计一共能发给多少人
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                     // 快乐水的总瓶数
    int used = 0;                 // 已经发出去的总瓶数
    for (int i = 1;; i++) {       // i是顾客编号，从1号开始
        int take = i * 2;         // 第i个顾客要领2*i瓶
        if (used + take > n) break;   // 加上他的就不够了，停止发放
        cout << i << " " << take << endl;
        used += take;             // 累加已发出的数量
    }
    return 0;
}

复杂度分析

第 i 个顾客领 2i 瓶，前 i 个顾客一共发 2+4+...+2i = i × (i+1) 瓶，所以能发出的人数大约等于根号 n，循环次数是 O(√n)；空间上只用了几个变量，额外空间复杂度是 O(1)。