two pointer + greedy、欧几里得算法

祝亲爱的”汉堡“（涵宝）生快~

双指针

此指针非彼指针 ~

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

例1

https://codeforces.com/problemset/problem/1007/A

解1

两个指针均从最大值的地方开始进行扫描，指针 代表当前需要被匹配的数字，指针 代表当前所剩数字中最大的数字，若 则 ，否则 指针继续向前移。

#include <bits/stdc++.h>
#define N 100007
using namespace std;

int a[N];

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int i = n, j = n, cnt = 0;
	while(i){
		if(a[i] < a[j]) {++cnt; --j;}
		i--;
	}
	cout << cnt << endl;
	return 0;
}

例2

https://codeforces.com/problemset/problem/1133/C

解2

#include <bits/stdc++.h>
#define N 200007
using namespace std;

int a[N];

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int i, j = n, cnt, Max = 0;
	for(int i = n; i > 0; --i){
		while(j > 0 && a[i] - 5 <= a[j]){
			cnt = i - j + 1;
			j--;
		}
		Max = max(Max, cnt);
	}
	cout << Max << endl;
	return 0;
}

欧几里得算法求最大公约数

利用的性质

模板

int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}

复杂度分析

$$\begin{cases} a < b &\rightarrow & change(b,a)\\ a > b &\rightarrow & a\mod b < \frac a 2 <b\\ \end{cases}\$$

复杂度为

https://blog.csdn.net/xiamentingtao/article/details/44702869