题目分析与思路提示

1. 解题思路

• 拆解问题：虽然烽火台很多，但我们只需要关注相邻的两座烽火台之间的距离。因为在 $P_i$ 和 $P_{i+1}$ 之间修塔，不会影响 $P_{i+1}$ 和 $P_{i+2}$ 之间的距离。
• 计算间距：对于每一对相邻的塔 $P_i$ 和 $P_{i+1}$，计算它们的间距 $D = P_{i+1} - P_i$。
• 判断与计算：
  • 如果 $D \le M$，说明这就够了，不需要修。
  • 如果 $D > M$，说明太远了，需要中间插塔。
  • 数学问题：这就变成了“把长度为 $D$ 的线段切成若干段，每段长度不能超过 $M$，最少切几刀（加几个点）？”
  • 公式推导：
    • 举例：$D=10, M=3$。需要分 $3, 3, 3, 1$，共 4 段，加 3 个点。
    • 举例：$D=9, M=3$。需要分 $3, 3, 3$，共 3 段，加 2 个点。
    • 段数 = $\lceil D / M \rceil$ （向上取整）。
    • 加点数 = 段数 - 1。
    • 编程公式：
      • 写法 A：(D - 1) / M （利用整数除法向下取整的特性）。
      • 写法 B：if (D % M == 0) ans += D/M - 1; else ans += D/M;。

2. 复杂度分析

• 我们需要遍历 $N$ 个塔之间的 $N-1$ 个间隔。
• 时间复杂度：$O(N)$。$N \le 1000$，非常快。
• 数据类型：$P_i$ 最大可达 $10^9$，在 int 范围内（int 最大约 $2 \times 10^9$）。但为了保险起见，或者如果以后计算总距离，使用 long long 也是好习惯。本题 int 足够。

参考代码 (C++14)

/**
 * 题目：烽火连天 (Beacon Fires)
 * 难度：GESP 4级
 * 知识点：数组遍历、贪心、整数除法逻辑
 */

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 提升 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 使用 vector 存储烽火台坐标
    // 也可以使用 int p[1005];
    vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
    }

    long long total_new_towers = 0;

    // 遍历每一个间隔
    // 有 N 个塔，所以有 N-1 个间隔
    for (int i = 0; i < N - 1; ++i) {
        int dist = p[i+1] - p[i];

        // 如果距离超过 M，需要增修
        if (dist > M) {
            // 计算需要增修的数量
            // 方法1：数学公式 (dist - 1) / M
            // 举例 dist=10, M=5 -> (9)/5 = 1。正确。
            // 举例 dist=11, M=5 -> (10)/5 = 2。正确。
            int count = (dist - 1) / M;
            
            total_new_towers += count;
        }
    }

    cout << total_new_towers << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// 标准解法
long long solve(int N, int M, const vector<int>& p) {
    long long ans = 0;
    for (int i = 0; i < N - 1; ++i) {
        int dist = p[i+1] - p[i];
        if (dist > M) {
            ans += (dist - 1) / M;
        }
    }
    return ans;
}

// 随机整数 [min, max]
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<int> p;

        // 构造不同类型的测试点
        if (i == 1) { 
            // 样例 1
            N=3; M=10; p={0, 10, 25};
        }
        else if (i == 2) { 
            // 样例 2
            N=4; M=5; p={10, 20, 22, 35};
        }
        else if (i == 3) {
            // 刚好不需要修 (所有间隔 = M)
            N = 10; M = 100;
            p.push_back(0);
            for(int k=1; k<N; k++) p.push_back(p.back() + 100);
        }
        else if (i == 4) {
            // 刚好需要修1个 (所有间隔 = M+1)
            N = 10; M = 100;
            p.push_back(0);
            for(int k=1; k<N; k++) p.push_back(p.back() + 101);
        }
        else if (i == 5) {
            // 刚好是倍数 (所有间隔 = 2M)
            N = 10; M = 50;
            p.push_back(0);
            for(int k=1; k<N; k++) p.push_back(p.back() + 100);
        }
        else if (i == 6) {
            // 极小间距 (都不需要修)
            N = 100; M = 1000;
            p.push_back(0);
            for(int k=1; k<N; k++) p.push_back(p.back() + randRange(1, 10));
        }
        else if (i == 7) {
            // 极大间距 (都需要修很多)
            N = 50; M = 2;
            p.push_back(0);
            for(int k=1; k<N; k++) p.push_back(p.back() + randRange(100, 200));
        }
        else {
            // 大规模随机
            N = 1000; M = randRange(10, 1000);
            p.push_back(randRange(0, 100));
            for(int k=1; k<N; k++) {
                // 随机生成下一个坐标，间隔在 1 到 2M 之间波动
                p.push_back(p.back() + randRange(1, 2 * M));
            }
        }

        // 写入输入
        fin << N << " " << M << endl;
        for(int k=0; k<N; k++) {
            fin << p[k] << (k == N-1 ? "" : " ");
        }
        fin << endl;

        // 写入输出
        fout << solve(N, M, p) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}