1. 优先队列
(1) 大根堆 (小顶堆)
priority_queue<int,vector<int>,greater<int>>q;
(2) 小根堆 (大顶堆)
- priority_queue<int, vector, Less>q;
- // 或者
- priority_queueq;
用法
- q.push(x);// 入队列
- q.pop();// 堆顶值
- q.back();// 队尾值
- q.pop();// 出队列
- q.empty();// 返回 q 是否为空, 空则返回 1, 否则返回 0
- q.size();// 返回 q 里元素个数
2. 排序
(1) 快排 (STL 万岁!\(QwQ\))
sort(a+1,a+n+1);//a 数组 1~n 从小到大排序
(2) 结构体排序
- // 定义
- struct node{
- int x,y;
- };
- node a[maxn];
- // 先从小到大按 x 值排序, 再从大到小按 y 值排序
- bool cmp(node s1,node s2){
- if(s1.x!=s2.x)return s1.x<s2.x;
- return s1.y>s2.y;
- }
- // 主函数内
- sort(a+1,a+n+1,cmp);
(3) 结构体内重载运算符
- struct node
- {
- int x,y;
- bool operator <(const node & a) const
- {
- return x<a.x;
- }
- };
(4) 归并排序
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #define _for(i,a,b) for(int i=a;i<=b;i++)
- #define maxn 500005
- using namespace std;
- typedef long long ll;
- int t[100005],ans=0;
- int n,a[100005];
- int read(){
- int f=1,ans=0;
- char c=getchar();
- while(!isdigit(c)){
- if(c=='-')f=-1;
- c=getchar();
- }
- while(isdigit(c)){
- ans=ans*10+c-'0';
- c=getchar();
- }
- return f*ans;
- }
- void gb(int a[],int l,int r){
- if(l==r)
- return;
- int mid=(l+r)/2;
- gb(a,l,mid);
- gb(a,mid+1,r);
- int i=l,j=mid+1,p=l;
- while(i<=mid&&j<=r){
- if(a[i]>a[j]){
- t[p++]=a[j++];
- ans+=mid-i+1; }
- else
- t[p++]=a[i++];
- }
- while(i<=mid)
- t[p++]=a[i++];
- while(j<=r)
- t[p++]=a[j++];
- for(i=l;i<=r;i++)
- a[i]=t[i];
- }
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- gb(a,1,n);
- cout<<ans<<endl;
- return 0;
- }
(5) 手写快排
- int a[101];
- void hand_write_quick_sort(int l,int r)
- {
- if(l>=r) return;
- else
- {
- int i=l;
- int j=r;
- int top=a[i];
- //a[i] 即为我们选择的 "点", 用于分割
- //(我们用的是这个点的值, 而不是位置.)
- while(i<j)
- {
- while(top<=a[j] && (i<j)) j--;
- //a[j] 比 top 大, 则换下一个进行比较
- a[i]=a[j];//"点" 的位置变为 a[j]
- while(a[i]<=top && (i<j)) i++;
- //a[i] 比 top 小, 则换下一个进行比较
- a[j]=a[i];//"点" 的位置变为 a[i]
- } // 小的往前去, 大的往后退.
- a[i]=top;
- hand_write_quick_sort(l,i-1);
- hand_write_quick_sort(i+1,r);
- }
- }
- *************************************
- //l~r 中第 k 大的数 (分治)
- LL get(int l, int r, int k)
- {
- if (l == r) return a[k];
- int u = l + rand() % (r-l+1);
- LL v = a[u];
- swap(a[l], a[u]);
- int i = l, j = r;
- while (i <j)
- {
- while (i <j && a[j]>= v) j--;
- if (i <j) { a[i] = a[j], i++; }
- while (i <j && a[i] <v) i++;
- if (i <j) { a[j] = a[i], j--; }
- }
- a[i] = v;
- while (i < (l+r)/2 && a[i] == a[i+1]) i++;
- if (k < i) return get(l, i-1, k);
- else if (k> i) return get(i+1, r, k);
- else return v;
- }
来源: http://www.bubuko.com/infodetail-2796178.html