快速排序

图解

先找到左哨兵作为基准数，右哨兵移动到比基准数小的数，左哨兵再移动到比右哨兵大的数。

交换两个数

重复上述过程，直到两哨兵相遇

相遇后将基准数与本数交换

这样就完成了第一轮交换，可以发现基准数已归位且在基准数左侧的数都比基准数小，右侧的数都比基准数大。只需分左右依次递归即可。

递归树

模板代码

void qsort(int l,int r){if(l>=r) return;int sol=a[l];int i=l,j=r;while(i!=j){while(a[j]>=sol&&i<j)j--;while(a[i]<=sol&&i<j) i++;if(i<j) swap(a[i],a[j]);}swap(a[l],a[i]);qsort(l,i-1);qsort(i+1,r);
}

例子

1. 第k小数1

只需向模板改为

void qsort(int l,int r){int sol=a[l];int i=l,j=r;while(i!=j){while(a[j]>=sol&&i<j)j--;while(a[i]<=sol&&i<j) i++;if(i<j) swap(a[i],a[j]);}swap(a[l],a[i]);if(k==i){p=a[i];return;}else if(k<i) qsort(l,i-1);else qsort(i+1,r);
}

因为我们只需第k小数，比k大或小不需要浪费时间去递归

2. 第k小数2
   通上只需将两组输入合并即可

归并排序

图解

第一步将原数组对半分，直到只剩下一个元素时停止。

第二步将分开的数组依次已小在前合并

模板代码

void merge(int head,int tail){int mid=(head+tail)/2;int s=head,e=mid+1,k=0;while(s<=mid&&e<=tail){if(a[s]>a[e]) temp[k++]=a[e++];else temp[k++]=a[s++];} while(s<=mid) temp[k++]=a[s++];while(e<=tail) temp[k++]=a[e++];k=0;for(int i=head;i<=tail;i++) a[i]=temp[k++];
}
void m_sort(int head,int tail){int mid=(head+tail)/2;if(head<tail){m_sort(head,mid);m_sort(mid+1,tail);merge(head,tail);}return;
}

例子

1. 求逆序对数
   

只需在合的过程中，只要这个数比另一个数小，那么比这个数小的数一定也比另一个数小，所以答案加上mid-s+1。

2. 查找最大和次大元素

void f(int l,int r,int &max1,int &max2){if(l==r) max1=a[l],max2=inf;else if(l+1==r){max1=max(a[l],a[r]);max2=min(a[l],a[r]);} else{int mid=(l+r)/2;int lmax1,lmax2;f(l,mid,lmax1,lmax2);int rmax1,rmax2;f(mid+1,r,rmax1,rmax2);if(lmax1>rmax1){max1=lmax1;max2=max(lmax2,rmax1);} else {max1=rmax1;max2=max(rmax2,lmax1);}} 
}	

我们只需在分的时候进行比较即可
3. 一次查找两元素

void f(int l,int r,int &min1,int &min2){if(l==r) min1=a[l],min2=inf;else if(l+1==r){min1=min(a[l],a[r]);min2=max(a[l],a[r]);} else{int mid=(l+r)/2;int lmin1,lmin2;f(l,mid,lmin1,lmin2);int rmin1,rmin2;f(mid+1,r,rmin1,rmin2);if(lmin1>rmin1){min1=rmin1;min2=min(rmin2,lmin1);} else {min1=lmin1;min2=min(lmin2,rmin1);}} 
}	

同理只需比较较小数即可

二分查找

模板代码

int f(int l,int r,int x){while(l<r){int mid=l+r>>1;//对半分if(a[mid]<x) l=mid+1;else r=mid;}if(a[l]==x) return l;else return -1; 
}

例子

1. 二分查找下界
   （1） 用二分进行比较

int f() {int l = 0, r = n + 1;while (l + 1 < r) {int mid = (r + l) / 2;if (a[mid] >= x)r = mid;elsel = mid;}return r;
}

（2） 用函数
二分查找下界
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

二分查找上界
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

代码
二分查找下界

#include<bits/stdc++.h>
using namespace std;
const int Max=1e6+5;
int a[Max];
int main() {int n,m;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&m);printf("%d",lower_bound(a+1,a+n+1,m)-a);return 0;
}

二分查找上界

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e6 + 5;
int a[Max];
int main() {int n, m;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}scanf("%d", &m);printf("%d", upper_bound(a + 1, a + n + 1, m) - a - 1);return 0;
}

2. 查找最接近的元素

int f(int l,int r,int x){while(l+1<r){int mid=l+r>>1;if(a[mid]<x) l=mid;else r=mid;}if(abs(x-a[l])<=abs(x-a[r])) return a[l];else return a[r];
}

分完后只需比较那个距离查找元素更近并返回即可

3.和为给定数

#include<bits/stdc++.h>
using namespace std;
const int Max=1e6+5;
int n,m,a[Max];
int f(int l,int r,int find){while(l<=r){int mid=l+r>>1;if(a[mid]==find) return a[mid];else if(a[mid]<find) l=mid+1;else r=mid-1;}return 0;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);scanf("%d",&m);for(int i=1;i<n;i++){if(a[i]>m/2) break;//剪枝if(f(i+1,n,m-a[i])){printf("%d %d",a[i],f(i+1,n,m-a[i]));return 0;} }printf("No");
}

利用二分将两重循环内的第二重循环改为二分优化时间

间接二分

间接二分是指需要将二分的mid用cheak改为比较值，cheak需要视情况而定

例子

1.二分法求函数的零点

在本题中cheak就是由上图而写

double check(double x){return pow(x,5)-15*pow(x,4)+85*pow(x,3)-225*pow(x,2)+274*x-121;
}

再由保留6位，以及f(1.5)>0,f（2.4）<0可写出以下代码

while(1){double mid=(l+r)/2;if(fabs(check(mid))<1e-6){printf("%.6lf",mid);return 0;}else if(check(mid)<=-1e-6) r=mid;else l=mid; }

2. 一元三次方程求解
   由ax³+bx²+cx+d＝0可写出cheak
   由 根的范围在-100至100之间 可知二分范围

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double cheak(double x){return a*pow(x,3)+b*x*x+c*x+d;
}
int main(){scanf("%lf %lf %lf %lf",&a,&b,&c,&d);for(double i=-100;i<100;i++){if(cheak(i)==0){printf("%.2lf ",i);continue;}if(cheak(i)*cheak(i+1)<0){double l=i,r=i+1,mid;while(r-l>0.001){mid=(l+r)/2;if(cheak(mid)*cheak(l)<0) r=mid;else l=mid;}printf("%.2lf ",mid);}}return 0;
}

3. 网线主管
   由题意知道我们需要切网线，所以可以二分切的长度。
   只需写cheak来返回切了多少根与输入比较

#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+5;
int a[Max],n,k;
int cheak(int mid){int sum=0;for(int i=1;i<=n;i++) sum+=a[i]/mid;//切网线 return sum;
}
int main(){scanf("%d %d",&n,&k);double x;int maxl=0;for(int i=1;i<=n;i++){scanf("%lf",&x);x=int(x*100+0.5);//转厘米 if(x>maxl) maxl=x;//找最长 a[i]=x;}int l=1,r=maxl,mid,ans;while(l<r){mid=l+r+1>>1;//求平均长度if(cheak(mid)>=k) l=mid,ans=mid;//保存答案 else r=mid-1;}if(cheak(l)>=k) printf("%.2lf",l/100.0); else printf("0.00"); return 0;
} 

4. 月度开销
   由题意我们可以明白我们可以二分fajo月的个数，再与输入比较，若过大了则左指针太小，若过小了则右指针太大

#include<bits/stdc++.h>
using namespace std;
const int Max=1e5+5;
int a[Max],n,m,maxn,sum;
int cheak(int mid){int sum=0,fajo=1;for(int i=1;i<=n;i++){if(sum+a[i]>mid) fajo++,sum=a[i];else sum+=a[i];}return fajo;
}
int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);maxn=max(maxn,a[i]),sum+=a[i];}int l=maxn,r=sum;while(l<r){int mid=l+r>>1;if(cheak(mid)>m) l=mid+1;else r=mid;} printf("%d",r);return 0;
} 

分治思考题

1.河中跳房子
我么这里可以二分石头个数，便有下cheak

bool cheak(int x) {int d = 0, cnt = 0;for (int i = 1; i <= N; i++) {if (a[i] - d < x) cnt++;else d = a[i];}if (L - d < x) cnt++;return cnt <= M;
}

再加上二分模板即可

while (l + 1 < r) {int mid = (l + r) / 2;if (cheak(mid)) l = mid;else r = mid;}

2.膨胀的木棍
我们看到这道题十分蒙圈
反正弦函数才cmath里

但看到提示后，立马明白了二分圆心角度数

	while(ri-le>1e-7){double mid=(le+ri)/2;double r=(mid*mid+l*l)/(2*mid);double ll=r*asin(l/r);if(ll>L) ri=mid;else le=mid;}

便有了这个二分代码
**可以将1e-7再改小，便更精准，但是时间也更长

**

队列

利用数组模拟

手写

1. 清空

void clear(){r=l;
}

2. 判断队列是否为空

bool empty(){return l==r;//1为空
}

3. 把整数 x 插入队尾

void push(int x){a[r]=x;r++;
}

4.队首元素出队列

void pop(){l++;
}

5. 获取队首元素的值。

int front(){return a[l];
}

例子

队列及其操作

STL 封装函数

定义

queue<类型（可以为接构体，队列）> 函数名

使用函数

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值，但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值，但不删除该元素

详解

• front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
• push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
• pop()：删除 queue 中的第一个元素。
• size()：返回 queue 中元素的个数。
• empty()：如果 queue 中没有元素的话，返回 true。
• emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
• swap(queue &other_q)：将当前 queue 中的元素和参数
• queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

例子

1. 周末舞会

#include<bits/stdc++.h>
using namespace std;
queue<int>s1;
queue<int>s2;
int main(){int m,n,k;scanf("%d %d %d",&m,&n,&k);for(int i=1;i<=m;i++) s1.push(i);for(int i=1;i<=n;i++) s2.push(i);while(k--){printf("%d %d\n",s1.front(),s2.front());s1.push(s1.front());s2.push(s2.front());s1.pop();s2.pop();}return 0;
}

使用两对列分别输出
2. 数集

#include<bits/stdc++.h>
using namespace std;
queue<long long> s1,s2,s3; 
int main(){int a,b,c,n;scanf("%d %d",&a,&n);s1.push(a);int tot=0;while(tot<n){tot++;b=s1.front()*2+1;c=s1.front()*3+1;s2.push(b);s3.push(c);if(s2.front()<s3.front()) s1.push(s2.front()),s2.pop();else if(s2.front()>s3.front()) s1.push(s3.front()),s3.pop();else s1.push(s3.front()),s2.pop(),s3.pop();s1.pop();if(tot==n-1) printf("%lld",s1.front());}return 0;
}

通过3个队列分别存储原数集与2x+1 和 3x+1数集。再比较大小依次存入原数集中

3. 取牌游戏

while(m<(k/n)){if(r%n==0){a[m++]=q.front();q.pop();}else q.pop();for(int i=1;i<=p;i++){q.push(q.front());q.pop();}r++;
}

按照题目要求模拟即可
4. 海港

#include<bits/stdc++.h>
using namespace std;
struct node{int s,t;
}h;
queue<node> q; 
int a[1000005],ans;
int main(){int n,t,k,x;scanf("%d",&n);while(n--){scanf("%d %d",&t,&k);while(!q.empty()){h=q.front();if(h.t+86400<=t){a[h.s]--;if(a[h.s]==0) ans--;q.pop();continue;}break;}for(int j=1;j<=k;j++){scanf("%d",&x);h.s=x,h.t=t;q.push(h);a[x]++;if(a[x]==1) ans++;}printf("%d\n",ans);}return 0;
}

这里便是在队列里打入结构体，然后用桶排思想进行查找不同国籍

补充优先队列

不为什么，就为凑字数多学yidia

定义

priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型，Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> > q;

一定要在 Functional后加空格，否则会被误认为右移

函数

与队列完全相同

栈

利用数组模拟

手写

1. 把栈置空

void clear(){l=0;
}

2. 判断栈是否为空

bool empty(){return l==0;
}

3. 把整数 x 插入栈顶

void push(int x){s[l++]=x;
}

4. 栈顶元素出栈

void pop(){l--;
}

5. 获取栈顶元素的值

int top(){return s[l-1];
}

例子

栈的基本操作

STL封装函数

定义

stack<数据类型> 函数名

函数

size( ) 返回栈中元素个数
top( ) 返回栈顶的元素
pop( ) 从栈中取出并删除元素
push(e) 向栈中添加元素e
empty( ) 栈为空时返回true

例子

1. 车站铁轨

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
stack<int> s;
int n,a[maxn];
int main(){scanf("%d",&n);int A=1,B=1,ans=0,sum=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);while(B<=n){if(A==a[B]) A++,B++,sum++,ans=max(ans,sum),sum--;else if(!s.empty()&&s.top()==a[B]) s.pop(),B++,sum--;else if(A<=n) s.push(A++),sum++;else{printf("no");return 0;}ans=max(sum,ans);}printf("yes\n%d",ans); return 0;
}

用左右指针控制栈的出入
2. 括号平衡

bool f(string a){int len=a.length(),cnt=1;char c;for(int i=0;i<len;i++){if(a[i]=='('||a[i]=='[') s.push(a[i]);else if(a[i]==')'){if(s.empty()) return 0;c=s.top();if(c=='(') s.pop();else return 0;}else if(a[i]==']'){if(s.empty()) return 0;c=s.top();if(c=='[') s.pop();else return 0;}}if(s.empty()) return 1;else return 0;
}

用栈进行检查为什么括号，如没有匹配则删除
3. 程序员输入问题
注意可在输入时输很多“#”

for(int i=0;i<l;i++){if(s.empty()) break;if(s.top()=='#'){s.pop();sum++;ll-=2;} else if(s.top()=='@'){ll-=s.size();break;} else {if(sum!=0) sum--,s.pop();else {b[z++]=s.top();s.pop();}}	
}

按照说明模拟即可

4. 溶液模拟器

while(n--){char ch;cin>>ch; 		if(ch=='P'){scanf("%d %lf",&v,&c);v0.push(v),c0.push(c);c1=(c1*v1+v*c)/(v+v1);v1+=v;printf("%d %.5lf\n",v1,c1);} else {if(v0.size()>1){c1=(c1*v1-v0.top()*c0.top())/(v1-v0.top());v1-=v0.top();v0.pop(),c0.pop();printf("%d %.5lf\n",v1,c1);} else printf("%d %.5lf\n",v1,c1);}
}

利用栈后进先出，进行撤销
5. 表达式求值

	while(ch=='+'||ch=='*'){scanf("%d",&t);t=t%10000;if(ch=='+') s.push(t);else {t=(s.top()*t)%10000;s.pop(),s.push(t);}ch=getchar();}while(!s.empty()){ans=(ans+s.top())%10000;s.pop();}

检索是+还是*，都不为则跳出
6.后缀表达式求值

#include<bits/stdc++.h>
using namespace std;
stack <int> a;
int main(){char s[105];while(~scanf("%s",s)){if(s[0]=='+'&&strlen(s)==1){int x=a.top();a.pop();int y=a.top();a.pop(),a.push(x+y);}else if(s[0]=='-'&&strlen(s)==1){int x=a.top();a.pop();int y=a.top();a.pop(),a.push(y-x);}else if(s[0]=='*'&&strlen(s)==1){int x=a.top();a.pop();int y=a.top();a.pop(),a.push(x*y);}else if(s[0]=='/'&&strlen(s)==1){int x=a.top();a.pop();int y=a.top();a.pop(),a.push(y/x);}else a.push(atoi(s));}printf("%d",a.top());return 0;
}

很经典题目。用栈存储数字，在判断为什么符号，进行运算

end