C语言实现一维城市轰炸最小炸弹数算法提交失败，求排查

A国与B国爆发战争，A国计划通过空袭摧毁B国首都。但战争突发，双方弹药储备不足。由于弹药有限，飞行员杰夫需携带恰好足够摧毁整座城市的炸弹数量，每枚炸弹只能投放在建筑上。

B国首都是一座一维城市，拥有n座建筑，每座建筑(i)位于x轴上的x(i)位置。杰夫必须摧毁城市中所有建筑，每枚炸弹的摧毁范围为k，即能摧毁落点周围距离≤k单位内的所有目标。

给定城市地图与炸弹范围k，计算摧毁整座城市所需的最少炸弹数（每座建筑必须处于至少一枚炸弹的摧毁范围内）。

输入格式 #

第一行包含两个空格分隔的整数n（城市中的建筑数量）和k（炸弹的摧毁范围）。
第二行包含n个空格分隔的整数，表示建筑在x轴上的位置。

输出格式 #

输出一个整数，表示摧毁城市所需的最少炸弹数。

约束条件 #

1 ≤ n,k ≤ 10^5
1 ≤ x ≤ 10^5

示例输入 #

4 2
1 2 3 4

示例输出 #

1

#include <stdio.h>
#include <stdlib.h>

/* Variables named according to the problem
 * n         - number of buildings
 * k         - range of bombs
 * buildings - Array containing the integer
 *             coordinates of the buildings
 */
int n, k, *buildings;

void getInput(void);
int isBuilding(int);
int nextBuilding(int);
int lastBuilding(int);

int main(void) {
 getInput();
 int bombs = 0;
 /* Loops through the x cordinates from building 1 to n
  * i - indicates the x coordinate where jeff is
  * j - indicates the bombed area
  * r - indicates the bomb range
  */
 for (int i = buildings[0], j = (buildings[0] - 1), r = k; i <= buildings[n - 1] || j < buildings[n - 1]; i++, r--) {
  /* When joel leaves bomb range coordinates behind */
  if (r == 0) {
   /* Bomb is only dropped on a building */
   while (!isBuilding(i))
    i--;
   /* Increment bombed area (back, position and front)*/
   j = i + k;
   bombs++;
   r = k + 1; // +1 because the loop makes r--
   /* next building beyond range
    * +1 because we need to leave all bombed area behind
    */
   i = nextBuilding(i + k + 1);
   /* if no building */
   if (i == 0)
    break;
   else
    i--; // the loop will make i++
  }
 }
 printf("%d\n", bombs);
 return 0;
}

/* Ascending comparison for qsort */
int compare(const void *a, const void *b) {
 const int *aa = a;
 const int *bb = b;
 return (*aa > *bb) - (*aa < *bb);
}

/* Gets input for n, k and buildings,
 * and sorts buildings
 */
void getInput(void) {
 if (scanf("%d %d", &n, &k) != 2) {
  fprintf(stderr, "input error\n");
  return;
 }
 buildings = calloc(sizeof *buildings, n);
 if (!buildings) {
  fprintf(stderr, "allocation error\n");
  return;
 }
 for (int i = 0; i < n; i++) {
  if (scanf("%d", &buildings[i]) != 1) {
   fprintf(stderr, "input error\n");
   return;
  }
 }
 qsort(buildings, n, sizeof *buildings, compare);
}

/* Returns 1 if it is a building,
 *  0 otherwise
 */
int isBuilding(int p) {
 for (int i = 0; i < n; i++) {
  if (buildings[i] == p)
   return 1;
 }
 return 0;
}

/* Returns position of next building greater or equal to p,
 * 0 if none available
 */
int nextBuilding(int p) {
 for (int i = 0; i < n; i++) {
  if (buildings[i] >= p)
   return buildings[i];
 }
 return 0;
}

/* Returns position of last building less or equal to p
 * 0 if none available
 */
int lastBuilding(int p) {
 for (int i = 0; i < n; i++) {
  if (buildings[i] == p)
   return buildings[i];
  else if (buildings[i] > p)
   return buildings[--i];
 }
 return 0;
}

代码说明 #

因为找不到合适的公式，我用了更直接的方法：

• 在main函数中，用i表示杰夫的位置，他向前移动k（炸弹范围）距离，若该位置有建筑则投放炸弹，否则后退到最近的建筑（题目明确要求炸弹只能投放在建筑上）。
• 随后将i移动到下一个未被轰炸覆盖的建筑，重复上述过程。
• 条件j < buildings[n - 1]用于处理i已超过最后一个建筑但仍有建筑未被覆盖的情况。

这段代码在本地运行正常，除题目示例外，我还测试了多组输入（如下），均得到预期输出：

输入:
6 2
1 2 3 4 5 6
输出: 2

输入:
10 2
2 3 8 16 17 18 19 20 21 22
输出: 4

但提交代码后所有测试用例均失败，请问我哪里出错了？

1. 核心问题：时间复杂度超标 #

你的代码中isBuilding、nextBuilding、lastBuilding都是线性遍历数组，当n达到1e5的最大值时，这些函数的时间复杂度是O(n)，而主循环本身也会遍历大量坐标，整体时间复杂度会达到O(n²)，完全无法通过时间限制，这是测试用例全部失败的主要原因。

2. 逻辑上的冗余与边界错误 #

• 主循环通过逐个坐标移动i的方式效率极低，完全没必要遍历所有坐标，直接操作已排序的建筑数组即可。
• nextBuilding返回0的逻辑有问题，如果建筑坐标本身包含0（虽然题目约束x≥1，但代码逻辑不严谨），会导致误判。

正确的贪心实现思路 #

因为建筑数组已经排序，我们可以用贪心算法高效解决：

1. 初始化炸弹数为0，当前处理的建筑索引idx=0。
2. 循环处理直到所有建筑被覆盖：
   • 找到第一个未被覆盖的建筑buildings[idx]。
   • 为了覆盖最多建筑，我们需要在能覆盖该建筑的最右侧建筑上投放炸弹：也就是找到最大的pos，使得pos ≤ buildings[idx] + k，且pos是建筑坐标。
   • 投放炸弹后，所有≤ pos + k的建筑都会被覆盖，找到第一个超过pos + k的建筑索引，更新idx为该索引。
   • 炸弹数加1。

修正后的代码 #

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    const int *aa = (const int*)a;
    const int *bb = (const int*)b;
    return *aa - *bb;
}

int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);
    int *buildings = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &buildings[i]);
    }
    qsort(buildings, n, sizeof(int), compare);
    
    int bombs = 0;
    int i = 0;
    while (i < n) {
        bombs++;
        // 找到能覆盖当前建筑的最右侧建筑（炸弹投放点）
        int pos = buildings[i] + k;
        while (i < n && buildings[i] <= pos) {
            i++;
        }
        // 回退到炸弹投放的建筑位置
        i--;
        // 跳过所有被当前炸弹覆盖的建筑
        pos = buildings[i] + k;
        while (i < n && buildings[i] <= pos) {
            i++;
        }
    }
    printf("%d\n", bombs);
    free(buildings);
    return 0;
}

说明 #

修正后的代码利用数组已排序的特性，通过线性遍历快速定位边界，时间复杂度为O(n log n)（主要来自排序），完全符合1e5数据量的时间要求，同时严格遵守炸弹必须投放在建筑上的规则。

内容的提问来源于stack exchange，提问作者Jore