北理工的恶龙（附qsort实例）
背景：最近，北理工出现了一只恶龙，它长着很多 头，而且还会吐火，它将会把北理工烧成废墟， 于是，校长下令召集全校所有勇士杀死这只恶龙。要杀死这只龙，必须把它所有的头都砍掉，每个勇士只能砍一个龙头，龙的每个头大小都不一样，一个勇士只有在身高不小于龙头的直径的情况下才能砍下它。而且勇士们要求，砍下一个龙头必须得到和自己身高厘米数一样的学分。校长想花 最少的学分数 杀死恶龙，于是找到你寻求帮助。
输入：第一行 龙头数 n , 勇士人数 m （ 1<=n, m<=100 ） 接下来 n 行，每行包含一个整数，表示龙头的直径 接下来 m 行，每行包含一个整数，表示勇士的身高 l
输出：如果勇士们能完成任务，输出校长需要花的最小费用；否则输 出 “bit is doomed! ”
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 |
|
| 1秒 | 64M | 0 |
| 测试用例 2 |
|
| 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出来了，痕迹还在。
欢迎大家指正可能存在的错误或提出更好的算法~~~
以上。