第1题：书架
John最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。
John共有N头奶牛(1 ≤ N ≤ 20,000)，每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000)，N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).
为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层，找出使用奶牛数目最少的解决方案吧。
时间限制：10000
内存限制：65536
输入
第1行：空格隔开的整数N和B 第2~N+1行：第i+1行为整数Hi
输出
能达到书架高度所使用奶牛的最少数目
样例输入
6 40
6
18
11
13
19
11
样例输出
3
答案：
#include <stdio.h>
#include <stdlib.h>
#define INF 999999999
#define N 20001
void myQuickSort(int x, int y, int a[]) {
int i = x, j = y, mid = a[(x + y) / 2];
while (i <= j) {
while (a[i] > mid)
i++;
while (a[j] < mid)
j--;
if (i <= j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (x < j)
myQuickSort(x, j, a);
if (i < y)
myQuickSort(i, y, a);
}
int main() {
int n, b;
int sum = 0;
int i;
scanf("%d %d", &n, &b);
int *a = (int*)malloc((N + 1) * sizeof(int));
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
myQuickSort(1, n, a);
for (i = 1; i <= n; i++) {
sum += a[i];
if (sum >= b)
break;
}
printf("%d\n", i);
free(a);
return 0;
}
这段代码是一个使用快速排序算法来解决问题的示例。下面是对代码的解析：
首先，我们包含了所需的标准库头文件
<stdio.h>和<stdlib.h>，用于输入输出和内存管理。定义了常量
INF和N，分别表示一个较大的无穷大值和数组a的最大长度。声明了自定义的快速排序函数
myQuickSort，它接受数组的起始和结束索引，以及数组本身作为参数。该函数使用分治法对数组进行原地排序。主函数
main开始执行。在主函数中，声明了变量
n和b，用于存储输入的整数值。变量sum用于计算数组元素的累加和，变量i用于循环迭代。使用
scanf函数依次读取输入的整数值n和b。动态分配内存，创建一个大小为
(N + 1)的整型数组a，用于存储输入的数组元素。这里使用malloc函数来分配内存。使用
for循环，从1到n依次读取输入的数组元素，并将其存储在数组a中。调用
myQuickSort函数，传入1和n作为数组的起始和结束索引，以及数组a本身。这将对数组a进行原地排序。使用
for循环遍历数组a，计算累加和并检查是否达到或超过b。一旦达到条件，跳出循环。使用
printf函数输出最终的计数器i的值，即第一个使得累加和大于等于b的位置。最后，使用
free函数释放动态分配的内存，即数组a所占用的内存。
这段代码的核心是快速排序算法，它通过递归地将数组划分为较小的子数组，并对子数组进行排序，最终实现整个数组的排序。然后，通过累加数组元素并检查累加和来确定满足条件的位置。这个示例展示了如何使用快速排序算法解决一个具体的问题。
第2题：抓牛
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
时间限制：2000
内存限制：65536
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
以下是使用搜索剪枝技术来解决抓牛问题的C语言代码：
#include <stdio.h>
#define MAX_N 100000
int minTime = MAX_N + 1; // 最小花费时间
void dfs(int N, int K, int time) {
// 剪枝条件：当时间已经超过最小花费时间或者超出范围时，停止搜索
if (time >= minTime || N > MAX_N || N < 0) {
return;
}
// 如果农夫抓住了牛，更新最小花费时间
if (N == K) {
if (time < minTime) {
minTime = time;
}
return;
}
// 递归搜索两种移动方式
dfs(N - 1, K, time + 1); // 从X移动到X-1
dfs(N + 1, K, time + 1); // 从X移动到X+1
dfs(N * 2, K, time + 1); // 从X移动到2*X
}
int main() {
int N, K;
// 读取输入
scanf("%d %d", &N, &K);
// 深度优先搜索
dfs(N, K, 0);
// 输出结果
printf("%d\n", minTime);
return 0;
}
该算法使用深度优先搜索的方法来搜索所有可能的移动路径，同时利用剪枝技术来提前终止搜索。在搜索过程中，维护一个最小花费时间的变量，如果当前时间超过最小花费时间或者农夫的位置超出范围，则停止搜索该路径。如果农夫抓住了牛，则更新最小花费时间。最后，输出最小花费时间作为解。
第3题：鸣人和佐助
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
输出
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
样例输入1
4 4 1
#@##
**##
###+
****
样例输入2
4 4 2
#@##
**##
###+
****
样例输出1
6
样例输出2
4
答案：
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAX_N 201
#define MAX_M 201
#define MAX_T 11
int n, m, sx, sy, st, minstep = INF;
int step[MAX_N][MAX_M][MAX_T];
int dx[] = {
0, 1, -1, 0};
int dy[] = {
1, 0, 0, -1};
char mp[MAX_N][MAX_M];
int vis[MAX_N][MAX_M];
void dfs(int x, int y, int t, int stp) {
// 边界条件判断
if (x < 1 || x > n || y < 1 || y > m || vis[x][y]) return;
if (t < 0) return;
if (stp >= minstep) return;
if (stp >= step[x][y][t]) return;
step[x][y][t] = stp;
// 处理当前位置的情况
if (mp[x][y] == '#') t--;
else if (mp[x][y] == '+') {
if (stp < minstep) minstep = stp;
return;
}
// 标记当前位置已访问
vis[x][y] = 1;
// 递归尝试四个方向的移动
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
dfs(nx, ny, t, stp + 1);
}
// 回溯，取消当前位置的访问标记
vis[x][y] = 0;
}
int main() {
// 读取输入
scanf("%d%d%d", &n, &m, &st);
getchar();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%c", &mp[i][j]);
if (mp[i][j] == '@') {
sx = i;
sy = j;
}
}
getchar();
}
// 初始化步数数组
memset(step, 0x3f, sizeof(step));
// 深度优先搜索
dfs(sx, sy, st, 0);
// 输出结果
if (minstep == INF) printf("-1");
else printf("%d", minstep);
return 0;
}
这段代码使用深度优先搜索（DFS）来解决问题。我们首先定义了常量INF表示无穷大的步数，并定义了地图的最大大小MAX_N和MAX_M，以及最大的查克拉数量MAX_T。
然后，我们定义了一些全局变量，包括地图的行数和列数n和m、起点的坐标sx和sy、起始的查克拉数量st，以及最小步数minstep和步数数组step。
接下来，我们定义了方向数组dx和dy，表示上下左右四个方向的偏移量。我们还定义了地图的字符数组mp和访问标记数组vis。
在dfs函数中，我们首先进行边界条件的判断，如果当前位置超出地图范围或已经访问过，则返回。如果查克拉数量小于0，则返回。如果当前步数大于等于最小步数，则返回。如果当前步数大于等于记录的步数数组中的步数，则返回。
然后，我们更新步数数组中当前位置和查克拉数量的步数值。接着，根据当前位置的情况进行处理：如果是墙壁，则查克拉数量减1；如果是佐助，则更新最小步数并返回。
接下来，我们标记当前位置为已访问，并尝试四个方向的移动，进行递归调用。每次递归调用时，我们更新新位置的坐标nx和ny，并将查克拉数量和步数加1。递归调用结束后，我们回溯，取消当前位置的访问标记。
在main函数中，我们首先读取输入的地图大小和起始查克拉数量。然后，我们使用双重循环读取地图的每个字符，并记录起点的坐标。
接下来，我们使用memset函数将步数数组初始化为一个较大的数值，表示未访问过的状态。
最后，我们调用dfs函数进行深度优先搜索，并输出最小步数结果。
如果最小步数minstep的值为INF，则说明无法到达佐助的位置，输出"-1"。否则，输出最小步数的值。
请注意，这段代码假设输入的地图是合法的，并且起点和终点都存在。如果输入的地图不满足这些条件，代码可能会出现问题。另外，代码中使用的是递归的深度优先搜索方法，对于较大的地图和查克拉数量可能会导致栈溢出的问题。在实际应用中，可能需要进行优化或使用其他搜索算法来解决这个问题。
第4题：献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
时间限制：100
内存限制：65536
输入
第一行是一个正整数T（1 <= T <= 10），表示一共有T组数据。 每一组数据的第一行包含了两个用空格分开的正整数R和C（2 <= R, C <= 200），表示地图是一个R×C的矩阵。 接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
输出
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
样例输入
3
3 4
.S…
###.
…E.
3 4
.S…
.E…
…
3 4
.S…
####
…E.
样例输出
5
1
oop!
答案：
以下是使用C语言编写的解决方案：
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX_R 202
#define MAX_C 202
char maze[MAX_R][MAX_C];
int dx[4] = {
-1, 1, 0, 0};
int dy[4] = {
0, 0, -1, 1};
struct Node {
int x, y, step;
};
struct Node queue[MAX_R * MAX_C];
int front, rear;
int bfs(int r, int c) {
int i, j, k;
int mi, mj;
int tx, ty;
bool is_t = false;
for (i = 1; i <= r; i++) {
for (j = 1; j <= c; j++) {
if (maze[i][j] == 'S') {
mi = i;
mj = j;
}
}
}
front = rear = 0;
queue[rear].x = mi;
queue[rear].y = mj;
queue[rear].step = 0;
rear++;
while (front < rear) {
struct Node t = queue[front++];
for (k = 0; k < 4; k++) {
tx = t.x + dx[k];
ty = t.y + dy[k];
if (tx < 1 || tx > r || ty < 1 || ty > c)
continue;
else if (maze[tx][ty] == '#')
continue;
else if (maze[tx][ty] == 'E') {
is_t = true;
return t.step + 1;
} else if (maze[tx][ty] == '.') {
queue[rear].x = tx;
queue[rear].y = ty;
queue[rear].step = t.step + 1;
rear++;
maze[tx][ty] = '#';
}
}
}
if (!is_t)
return -1;
}
int main() {
int t, r, c;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &r, &c);
memset(maze, 0, sizeof(maze));
for (int i = 1; i <= r; i++) {
scanf("%s", &maze[i][1]);
}
int result = bfs(r, c);
if (result == -1)
printf("oop!\n");
else
printf("%d\n", result);
}
return 0;
}
该解决方案使用广度优先搜索（BFS）算法来找到阿尔吉侬到达奶酪的最短路径。在BFS过程中，使用队列来保存待处理的节点，并逐步扩展到相邻的可通行节点，直到找到奶酪或无法到达。
![[自动化分布式] Zabbix自动发现与自动注册](https://img-blog.csdnimg.cn/direct/d50c51797be144f5a0b15a9f3ff68419.png)
