算法竞赛最最最常用的8个C++算法

?Algorithm

头文件：

#include<algorithm>

1、sort()函数：内置原理为快排——时间复杂度O(n*logn)

int a[5] = {4,2,1,3,5};
vector<int> b(a,a+5);
sort(a,a+5);//搭配数组  从小到大排序
sort(b.begin(),b.end());//搭配容器，如vector
sort(a,a+5,greater());//从大到小排序

2、find()：（寻找元素）

//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，
//若存在返回其在向量中的位置
find(a.begin(),a.end(),10);

3、erase()：（删除元素）

//从c中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能等于c.end()
c.erase(p);
//从c中删除迭代器对b和e所表示的范围中的元素，返回e
c.erase(v.begin(),v.end());

4、reverse()：（反转序列）

vector<int>v={1,2,3,4,5};
reverse(v.begin(),v.end());//v为{5，4，3，2，1}；

5、max、min ：? （取较大较小值）

max(a,b);//返回a，b较大值
min(a,b);//同理

6、swap()：（交换）

swap(a,b)//交换a和b

7、__gcd()：（最大公约数）

scanf("%d %d",&n,&m);
int k=__gcd(n,m);//最大公约数
printf("%d ",k);
printf("%d", n * m / k); //最小公倍数

8、lower_bound();upper_bound()

使用前一定要先排序

lower_bound()：返回第一个>=target的数的地址；

upper_bound()：返回第一个>target的数的地址；

int r=upper_bound(v.begin(),v.end(),target)-v.begin();//减去首地址，返回下标
int l=lower_bound(v.begin(),v.end(),terget)-v.begin();

此外，再附加一个?next_permutation?（全排列）

作用：
将当前排列更改为全排列中的下一个排列。
如果当前排列已经是全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。

// 1 结合 数组
int a[] = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < 5; i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a, a + 5));

// 2结合 vector
vector<int> a = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < a.size(); i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a.begin(), a.end()));

?

?

?

?