P4425 短信计费（基础）

解题思路

每条短信最多70个字，超过70字就要按每70字一条拆成多条，每条0.1元。所以关键是算"一个字数为w的短信要算几条"：这就是 w 除以70向上取整。向上取整的意思是除不尽也要进一位，比如147字要算3条（70+70+7），72字要算2条（70+2）。向上取整有个巧妙的公式：(w+69)/70。为什么？当w能被70整除时，比如w=140，(140+69)/70=209/70=2，正好是2条；当w比70的倍数大一点时，比如141，(141+69)/70=210/70=3，自动进了一位；恰好整除时加上69也不会多算，因为(140+69)只比140多69，除以70还是2。把n条短信的条数都加进t，最后每条0.1元，总资费就是 t×0.1。因为要精确到小数点后1位，我们用 printf("%.1f") 输出。边界情况：如果某条短信恰好70字，只算1条；如果字数少于70，比如39字，也算1条，因为(39+69)/70=108/70=1。

参考代码

// 程序用途：按每条短信70个字计费，计算n条短信的总资费（保留1位小数）
#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);                // 读入短信总次数
    int t = 0;                      // 短信总条数（70字算一条）
    for (int i = 0; i < n; i++) {
        int w;
        scanf("%d", &w);            // 每次短信的字数
        t += (w + 69) / 70;         // 字数除以70向上取整，得到短信条数
    }
    printf("%.1f\n", t * 0.1);      // 每条0.1元，保留1位小数输出总资费
    return 0;
}

复杂度分析

用for循环把n条短信各处理一次（n≤1000），每一条只做一次除法和一次累加，所以时间复杂度 O(n)；只用t、w几个变量，额外空间复杂度 O(1)。