Posted on 2010-08-19 16:54
Kevin_Zhang 阅读(227)
评论(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上面的。