【程序设计基础_C语言】北理工的恶龙(附qsort实例)
北理工的恶龙(附qsort实例)
背景：最近，北理工出现了一只恶龙，它长着很多 头，而且还会吐火，它将会把北理工烧成废墟， 于是，校长下令召集全校所有勇士杀死这只恶龙。要杀死这只龙，必须把它所有的头都砍掉，每个勇士只能砍一个龙头，龙的每个头大小都不一样，一个勇士只有在身高不小于龙头的直径的情况下才能砍下它。而且勇士们要求，砍下一个龙头必须得到和自己身高厘米数一样的学分。校长想花 最少的学分数 杀死恶龙，于是找到你寻求帮助。
输入：第一行 龙头数 n , 勇士人数 m ( 1<=n, m<=100 ) 接下来 n 行，每行包含一个整数，表示龙头的直径 接下来 m 行，每行包含一个整数，表示勇士的身高 l
输出：如果勇士们能完成任务，输出校长需要花的最小费用；否则输 出 “bit is doomed! ”
测试输入期待的输出时间限制内存限制额外进程
测试用例 1
以文本方式显示
23↵
5↵
4↵
7↵
8↵
4↵
1秒
64M
0
测试用例 2
以文本方式显示
21↵
5↵
5↵
10↵
以文本方式显示
bitisdoomed!↵
1秒
64M
0
【分析】
问题抽象为两个数组，dragon和soldier，分别存储勇士的身高和龙头的直径。
如果数组soldier中某个值大于等于dragon某个值，即斩龙头成功，勇士身高计入sum。
要求“耗费学分”最少，即优先让身高比较低的勇士去当前剩下最小的斩龙头，所以先将两个数组分别从小到大排序。
当有龙头剩下(i <= n)且没有勇士可以斩龙头(j > m)时，失败。
需要注意的一点，如果当前勇士成功斩龙，那么既要向下一个龙头移动，又要向下一个勇士移动(因为一个勇士只能斩一个龙头)。
【代码】
//E026：【大学】北理工的恶龙
#include"stdio.h"
#include"stdlib.h"
int cmp(const void *a, const void *b) //排序函数
{
return *(int *)a - *(int *)b;
}
int cmp(const void *a, const void *b);
int main()
{
int n;//n是龙头数
int dragon[102] = { 0 };//dragon是龙头的直径
int m;//m是勇士人数
int soldier[102] = { 0 };//solider是勇士的身高
int sum = 0;//sum是花费的总学分数(斩龙的用时身高之和)
int i, j;
scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++)//输入龙头直径
{
scanf("%d", &dragon[i]);
}
for (i = 1; i <= m; i++)//输入勇士身高
{
scanf("%d", &soldier[i]);
}
qsort(dragon+1, n, sizeof(int), cmp); //调用函数，为dragon排序
qsort(soldier+1, m, sizeof(int), cmp); //调用函数，为soldier排序
/*
for (i = 1; i <= n; i++)//监视排序是否成功 -- 成功
{
printf("dragon[%d] = %d\n", i, dragon[i]);
}
*/
for (i = 1, j = 1; i <= n; i++)
{
//printf("i = %d\n", i);//监视i的值
if (j > m)
{
//printf("Failure：i = %d, j = %d\n", i, j);//监视失败时的状况
goto failure;
}
if (soldier[j] >= dragon[i])//如果当前的勇士能够斩龙头
{
sum += soldier[j];
j++;//成功则该勇士计入sum，并比较下一个勇士和下一个龙头
//printf("勇士i = %d斩龙j = %d成功！\n", i, j);//标明斩龙头成功
continue;
}
else//如果当前的勇士不能斩龙，那么循环直到斩龙成功，或者失败
{
while (soldier[j] < dragon[i])//如果当前的勇士不能斩龙，该勇士不计入sum，并比较下一个勇士
{
j++;
if (j > m)//如果没有下一个勇士了，则失败
goto failure;
else if (soldier[j] >= dragon[i])//比较下一个勇士
{
sum += soldier[j];
j++;
break;//成功则该勇士计入sum，并比较下一个勇士和下一个龙头
}
else
{
continue;//如果该勇士也失败，比较下一个勇士
}
}
}
}
printf("%d\n", sum);
return 0;
failure:
printf("bit is doomed!\n");
return 0;
}//main
【qsort：快速排列进行排序】
#include"stdlib.h"//qsort需要这个头文件
int cmp(const void *a, const void *b);//函数声明
int cmp(const void *a, const void *b)//函数定义
{
return *(int *)a - *(int *)b; //从小到大如果从大到小，则将此行的a和b调换即可
}
int main()
{
int dragon[102];
qsort(dragon + 1, n, sizeof(int), cmp);//调用函数，令dragon数组从dragon[1]从小到大排序并覆盖原数组
//上一行的各参数：1 待排序数组首地址 2 数组中待排序元素数量 3 各元素的占用空间大小 4 指向函数的指针
return 0;
}
【感悟】
其实看起来并没有那么难，只是自己在读题的时候把自己绕进去了。
自己在本地测试的时候，发现在某种情况下，勇士斩龙头成功后，勇士忘记向下一个移动。
所以花了几分钟debug出来了，痕迹还在。
欢迎大家指正可能存在的错误或提出更好的算法~~~
以上。
