ACM - 暑期第二天：貪心算法 及 字典樹

天天有AC，日后必歡喜。今天折磨了一整天，收獲很多。大二都在學(xué)java，算法這部分一直很薄弱，沒有針對(duì)地去訓(xùn)練。今天做了兩道題：農(nóng)大ACM1364?和 杭電1364，專門地訓(xùn)練貪心算法和優(yōu)化串操作的字典樹，自己對(duì)于貪心算法還是只知皮毛。看似簡單的原理，但是一葉障目而不見泰山，還要專門地去好好訓(xùn)練下。

把自己折磨得不成人樣，別人才會(huì)把你當(dāng)成人看。

看題：

農(nóng)大acm隊(duì)有一位郭先生，他特別的貪吃，每天都想著怎么用有限的money買到最多份的零食。愁死了，聽說acm選拔賽又開始了，聰明的你們就幫幫他吧。?
????
	假如郭先生有50塊錢，有不知道個(gè)數(shù)的n種零食的價(jià)錢及份數(shù)(假設(shè)份數(shù)都是有限的)，（假設(shè)郭先生對(duì)每種零食的喜歡程度都是一樣的，且在每種零食的總共的份數(shù)里面，可以隨意買多少份）如?10?2?20?5?30?5.....（數(shù)據(jù)的意思是第一份總共有兩份，總共花費(fèi)10塊錢）這樣郭先生就可以得到最多10份零食（10份，第一種2份，第二種5份，第三種3份）

知道使用貪心算法算，但是這里面有兩個(gè)難題：

1. 輸入：沒有確定零食價(jià)格和分?jǐn)?shù)的個(gè)數(shù)，需要根據(jù)輸入來判斷。

2. 以平均價(jià)格來求貪心，這邊用三個(gè)數(shù)組的話排序后就不能和所知道的價(jià)錢和分?jǐn)?shù)對(duì)應(yīng)起來。

這兩個(gè)難題折磨了我很久，最后終于把它解決了，腦袋笨就是沒辦法。

貼出代碼：

#include#includeusing?namespace?std;
double?t[100];
double?m[100];
struct?PA{
	double?v;	
	int?count;
}pa[100];//使用結(jié)構(gòu)體數(shù)組，以便于把數(shù)值對(duì)應(yīng)起來
int??main(){
	int?j,?i,?flag;
	char?ch;
	double?n,?temp,?total;
	while(cin?>>?n){
		i?=?0,?j=0,?total=0;
		do{
			cin?>>?m[i]?>>?t[i];
			pa[i].v?=?m[i]?/?t[i];
			pa[i].count?=?i;
			i++;
		}while((ch?=?getchar())?!=?'n');?//?做循環(huán)，知道遇到空格鍵
		
		for(j=0;?j<i;?j++)		//使用冒泡排序，這邊結(jié)構(gòu)體數(shù)組，用不了sort()，不知為何
			?for(int?n=j+1;?n?pa[n].v){
					temp?=?pa[j].v;
					pa[j].v?=?pa[n].v;
					pa[n].v?=?temp;
					flag?=?pa[j].count;
					pa[j].count?=?pa[n].count;
					pa[n].count?=?flag;
				?}
		j?=?0;
		while(n?>=?m[pa[j].count]){		//接下來的兩個(gè)循環(huán)是從最小平均價(jià)格算起
			n?=?n?-?m[pa[j].count];
			total?+=?t[pa[j].count];
			j++;
		}
		for(int?k=j;?k=?pa[k].v){
				n?=?n?-?pa[k].v;
				total++;
			}
		}
		
		cout?<<?total?<<?endl;
		//for(j=0;?j<i;?j++)
		//	cout?<<?pa[j].v?<<?endl;
	}
	return?0;
}