如何确定我的城市轰炸算法的破坏效率？[关闭]

问：

这是我想在 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

链接到问题。

问题也可以在以下位置找到：code.dcoder.tech >挑战>硬>耗尽弹药

我的解决方案

#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;
}

解释

我采取更直接的方法解决这个问题，因为试图找到一个公式似乎是不可能的。

我主要使用杰夫的位置，他向前移动（炸弹射程）距离，然后在那里放置炸弹，如果当时有建筑物，或者回到最后一栋建筑物。（这个问题明确提到炸弹只能放置在建筑物上）。ik

然后我移动到下一个未被轰炸的建筑物并重复上述过程。i

条件是当有剩余的建筑物但无法满足（已超过最后一栋建筑物）时。j < ni <= buildings[n - 1]i

问题

代码在我这边似乎运行良好。

除了问题中的输入之外，我还测试了各种输入（如下所示），并得到了所需的输出。

Input:
6 2
1 2 3 4 5 6
Output: 2

Input:
10 2
2 3 8 16 17 18 19 20 21 22
Output: 4

尽管当我提交问题时，所有测试都失败了。

我哪里出错了？