蚂蚁爬树问题没有思路

Question

有k个蜗牛，各有它们不同的爬行速度，通常都是从树根向上爬，若树高为h米，如第i只蜗牛按它的速度每次向上爬ni米，向下滑mi米．试输出每只蜗牛直到爬到树顶的过程中爬过每一米线经过的次数 。统计树的每一米线都有多少次蜗牛爬过。要求：采用链表实现．采用顺序栈实现哪只蜗牛爬得最快，请输出它的爬行速度规律。

Answer 1

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

// 定义链表节点
typedef struct Node {
  int pos; // 当前位置
  int times; // 爬过的次数
  struct Node *next; // 指向下一个节点的指针
} Node;

// 定义链表
typedef struct List {
  Node *head; // 头结点
} List;

// 初始化链表
List *initList() {
  List *list = (List*)malloc(sizeof(List));
  list->head = NULL;
  return list;
}

// 在链表的指定位置插入节点
void insertNode(List *list, int pos) {
  Node *node = (Node*)malloc(sizeof(Node));
  node->pos = pos;
  node->times = 1;
  node->next = NULL;

  if (list->head == NULL) {
    // 如果链表为空，则将新节点作为头结点
    list->head = node;
  } else {
    // 否则，遍历链表找到合适的位置插入新节点
    Node *curr = list->head;
    while (curr->next != NULL && curr->pos < pos) {
      curr = curr->next;
    }
    if (curr->pos == pos) {
      // 如果找到了对应的位置，则将爬过的次数加 1
      curr->times++;
    } else {
      // 否则，在当前节点的前面或后面插入新节点
      node->next = curr->next;
      curr->next = node;
    }
  }
}

int main() {
  int h, k;
  scanf("%d%d", &h, &k);

  // 创建链表
  List *list = initList();

  // 循环处理每只蜗牛
  for (int i = 0; i < k; i++) {
    int n, m;
    scanf("%d%d", &n, &m);

    int pos = 0; // 蜗牛的当前位置
    // 循环处理蜗牛的爬行过程
    while (pos < h) {
      pos += n;
      if (pos >= h) {
        // 如果超出了树的高度，则退出循环
        break;
      }
      insertNode(list, pos); // 在链表中插入新节点
      pos -= m;
      if (pos < 0) {
        // 如果位置小于 0，则将位置设为 0
        pos = 0;
      }
      insertNode(list, pos); // 在链表中插入新节点
    }
  }

  // 遍历链表，输出每一米线的爬过次数
  Node *node = list->head;
  while (node != NULL) {
    printf("%d: %d\n", node->pos, node->times);
    node = node->next;
  }

  return 0;
}