Posted on 2010-08-19 16:54
Kevin_Zhang 閱讀(265)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
排序
http://acm.pku.edu.cn/JudgeOnline/problem?id=1065排序+貪心
排序方式可以使用fastsort()，這個可以使用模板，也可以自己寫，還可以使用STL的sort()函數。
語法:
void sort();
void sort( Comp compfunction );
|
sort()函數為鏈表排序，默認是升序。如果指定compfunction的話，就采用指定函數來判定兩個元素的大小。
首先實現這個排序有兩種方式，一個自己定義一個返回值為bool的比較函數。
一個是自己定義類中的<操作函數。
第一種方式可以簡單寫為。
bool cmp(node x,node y)
{
return x.key1<b.key1;
}
sort(vec.begin,vec.end.cmp);
這種排序是從小到大的，也就是如果cmp(a,b)為真，則a一定在b的前面，如果
cmp(a,b)和cmp(b,a)都為false.的話，也就是a.key1==b.key1,則他們的先后順序則是不一定的，可能a在b前面，也可能b在a前面。
也就是說這種排序算法是不穩定的。
第二種方式
struct node{
int key1;
int key2;
book operator <(const node &m)
{
return key1<m.key1;
}
}
這樣就不用自己定義比較函數。
對與sort()排序是不穩定的，正如前面說的，如果需要穩定排序的話，可以使用
stable_sort，它可以保證相等的元素原來的相對次序是不變的。
另外貪心選擇時，要逐步選擇，具體代碼可以參考Discuss上面的。