C语言实现最小炸弹数算法题提交全失败，请求错误排查

A国与B国爆发战争，A国计划空袭摧毁B国首都。由于弹药储备不足，飞行员Jeff必须携带恰好数量的炸弹，且每个炸弹只能投放在建筑位置上。

B国首都是一维城市，包含n栋建筑，每栋建筑位于x轴的x(i)位置。每个炸弹的破坏范围为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;
}

我采用模拟思路：用i表示Jeff的位置，移动k距离后，若当前位置是建筑则投弹，否则回退到最近的建筑；投弹后移动到未被覆盖的下一栋建筑，重复该过程。

本地测试多个用例均得到正确结果，例如：
输入：

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三个函数都用线性遍历数组的方式实现，时间复杂度为O(n)。当n达到1e5的上限时，主循环结合这些线性查找会让整体时间复杂度变为O(n²)，完全超出题目时间限制，导致超时，这是所有测试用例失败的核心原因。

由于数组已经通过qsort排序完成，这些查找操作应该改用二分查找，将时间复杂度降到O(logn)。

2. 主循环的冗余逻辑 #

主循环通过逐个坐标移动模拟Jeff的位置，当建筑坐标跨度极大时（比如从1直接跳到1e5），循环会执行1e5次，完全没必要。实际上不需要遍历每个坐标点，直接处理建筑的位置即可。

正确的贪心思路应该是：

• 从第一栋建筑开始，找到最远的能被当前炸弹覆盖的建筑，选择最优投弹点（让覆盖范围最大）；
• 接着找到第一个不在该炸弹覆盖范围内的建筑，重复上述步骤。

修正后的代码示例 #

#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;
    if (scanf("%d %d", &n, &k) != 2) {
        fprintf(stderr, "input error\n");
        return 1;
    }

    int *buildings = malloc(n * sizeof(int));
    if (!buildings) {
        fprintf(stderr, "allocation error\n");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        if (scanf("%d", &buildings[i]) != 1) {
            fprintf(stderr, "input error\n");
            free(buildings);
            return 1;
        }
    }

    qsort(buildings, n, sizeof(int), compare);

    int bombs = 0;
    int idx = 0;
    while (idx < n) {
        bombs++;
        // 找到当前建筑能覆盖的最远位置
        int target = buildings[idx] + k;
        // 二分查找最后一个被覆盖的建筑索引
        int left = idx, right = n - 1;
        int last_covered = idx;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (buildings[mid] <= target) {
                last_covered = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 找到下一个需要处理的建筑（超出当前炸弹覆盖范围的第一个）
        target = buildings[last_covered] + k;
        left = last_covered + 1;
        right = n - 1;
        int next_idx = n;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (buildings[mid] > target) {
                next_idx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        idx = next_idx;
    }

    printf("%d\n", bombs);
    free(buildings);
    return 0;
}

修正说明 #

1. 抛弃逐个坐标遍历的逻辑，直接通过建筑索引处理，大幅减少循环次数；
2. 用二分查找替代线性查找，将整体时间复杂度降到O(nlogn)，符合1e5数据量的要求；
3. 严格遵循贪心策略：每次投弹选择能覆盖最多剩余建筑的位置，确保炸弹数量最少。

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