【程序設計基礎_C語言】北理工的惡龍，程序設計基礎_c

【程序設計基礎_C語言】北理工的惡龍，程序設計基礎_c

北理工的惡龍（附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出來了，痕跡還在。
歡迎大家指正可能存在的錯誤或提出更好的算法~~~


以上。