算法题整理——倍增

发表于 | 分类于 |

引子

有一个数组a，里面存有n个非负整数，现在定义一次查询：给出整数t，要求找出最大的数组下标k，使得数组a在k的前缀和小于等于t。

解法

首先预处理a，计算出前缀和数组s，可以对每个查询进行二分查找，时间复杂度是O(logn)。

蓝书的作者指出二分思想虽然在平均情况下表现很好，但是面对大量查询结果非常小的情况下会进行很多次无用的查找，所以给出了倍增的思想：

1.令pos = 0，p = 1；

2.比较s[pos + p]和t的大小，如果t大，那么pos += p，p *= 2；否则，p /= 2。

3.重复2，直到p小于0。

这个算法的时间复杂度是O(logk)，k是最终的答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;
int a[N];
int s[N];

int main(){
	memset(s, 0, sizeof(s));
	int n, t;
	scanf("%d %d", &n, &t);
	scanf("%d", &a[0]);
	s[0] = 0;
	for(int i = 1; i < n; ++i) scanf("%d", &a[i]), s[i + 1] = s[i] + a[i];
	
	int p = 1;
	int sum = 0;
	int pos = 0;
	while(p){
		if(pos + p >= n) p /= 2;
		else if(sum + s[pos + p] - s[pos] <= t) sum += (s[pos + p] - s[pos]), pos += p, p *= 2;
		else p /= 2;
	}
	
	printf("%d\n", pos);
	
	return 0;
}

ST算法

基于倍增思想的ST算法可以在一次O(nlogn)复杂度的预处理之后，用O(1)的时间去回答区间最大值的问题。

算法思路

使用二维数组b[i][j]存储一维数组a[n]中下标从i到i + (1 << j) - 1的闭区间内的最大值，这样查询区间[l, r]上的最大值时，我们首先对区间长度取以2为底的对数：

int k = log(r - l + 1) / log(2)

由于k对结果向下取整，所以1 << k的值将小于等于真正的区间长度k，但一定大于k / 2，这样，区间[l,l + (1 << k)]和区间[r - (l << k)]的并集必然覆盖了[l, r]，所以结果直接是：

max(b[l][k], b[r - (1 << k)][k])

那么，如何得到数组b呢？遍历区间左端点和区间大小，大的区间的值可以由两个小区间值的最大值得到。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int a[N];
int n;
int b[N][N];

void prework(){
	for(int i = 0; i < n; ++i) b[i][0] = a[i];
	int l = log(n) / log(2) + 1;
	//printf("%lf, %lf, %lf, %d\n", log(n), log(2), log(n)/log(2), l);
	for(int j = 1; j < l; ++j)
		for(int i = 0; i + (1 << j) <= n; ++i){
			//printf("b[%d][%d] = max(b[%d][%d] = %d, b[%d][%d] = %d)\n", i, j, i, j - 1, b[i][j - 1], i + (1 << (j - 1)), j - 1, b[i + (1 << (j - 1))][j - 1]); 
			b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
		}	
}

void query(int l, int r){
	if(l > r) swap(l, r);
	if(r >= n) printf("to large\n");
	else {
		int k = log(r - l + 1) / log(2);
		printf("%d\n", max(b[l][k], b[r - (1 << k)][k]));
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
	prework();
	/*
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < log(n) / log(2); ++j)
			printf("%d %d %d\n", i, j, b[i][j]);
	*/
	printf("query:\n");
	int l, r;
	scanf("%d %d", &l, &r);
	while(l && r){
		query(l - 1, r - 1);
		scanf("%d %d", &l, &r);
	}
	return 0;
}

CH0601-GeniusACM

描述

给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:

从集合 S 中取出 M 对数(即 2∗M 个数，不能重复使用集合中的数，如果 S 中的整 数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值 就称为集合 S 的“校验值”。

现在给定一个长度为 N 的数列 A 以及一个整数 T。我们要把 A 分成若干段，使得 每一段的“校验值”都不超过 T。求最少需要分成几段。

数据范围

T ≤ 12

1 ≤ n, m ≤ 5e5

0 ≤ k ≤ 1e18

0 ≤ Pi ≤ 2^20

思路

首先，”校验值“必然要这样取：先取出最大的数和最小的数，然后做差的平方，再从剩下的集合里面取最大最小的数，以此类推。证明很简单，列个式子就能得出结论。

之后，我们想的是已知区间左端点L，如何确定最大的右端点R。这里用到了倍增的思想：先设置变量p的值是1，令R向后移动p个数字，如果新区间依然满足条件，更新R并倍增p，否则，p减半。直到p为0，此时已经找到了最大的右端点。

如何判断是否满足条件呢，我们需要对新区间的数进行排序，快速排序的时间复杂度是O(nlogn)，如果使用快速排序，分析可知：对于每个区间，p的值变为0的过程中，最多循环logn次，每次对长度为R-L的区间进行排序，R-L最坏情况下数量级是n，所以复杂度是O(n(logn)^2)。

使用上面的算法在CH上提交可以得90分。

我们注意到R的值是只增不减的，也就是说对于L-R这一段，里面的数字一定会包含在最终的区间里面。我们对L-R这段已经排序完成过之后，可以不用再重复排序，我们只对R+1到R+p的数组排序，然后把前后两段有序数组归并。

注意这里的归并并不是在原数组里面进行的，因为R+1到R+p这段，我们还不确定它在不在最终的数组里面，所以如果在原数组里面归并好了，如果检验发现加上这一段之后不能满足要求，我们还要把数组恢复回去，会麻烦。

这样做，快速排序的规模会缩小为∑plogp，p可以看作n的二进制展开，所以快速排序总复杂度是nlogn，比上面的方法要快。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e5 + 5;

long long a[N];
long long b[N];
long long c[N];

int n, m;
long long k;

bool judje(int l, int r){
	int p = l;
	int q = r;
	long long sum = 0;
	for(int i = 0; i < m; ++i){
		if(p >= q) break;
		sum += (b[q] - b[p]) * (b[q] - b[p]);
		++p, --q;
	}
	return sum <= k;
}

void Merge(int l, int mid, int r){
	int p = l;
	int q = mid + 1;
	for(int i = l; i <= r; ++i){
		if(p > mid) b[i] = c[q++];
		else if(q > r) b[i] = a[p++];
		else if(a[p] > c[q]) b[i] = c[q++];
		else b[i] = a[p++];
	}
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d %d %lld", &n, &m, &k);
		for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);
		int ret = 0;
		int l = 0;
		int r = l;
		int p = 1;
		int lastsort = 0;
		while(true){
			while(p){
				if(r + p >= n) p /= 2;
				else {
					for(int i = r + 1; i <= r + p; ++i) c[i] = a[i];
					sort(c + r + 1, c + r + p + 1);
					Merge(l, r, r + p);
					if(judje(l, r + p)){
						r += p;
						p *= 2;
						for(int i = l; i <= r; ++i) a[i] = b[i];
					}
					else p /= 2;
				}
			}
			++ret;
			if(r == n - 1) break;
			l = r + 1;
			r = l;
			p = 1;
		}
		printf("%d\n", ret);
	}
	return 0;
}

注

本题用二分的复杂度是多少？

我们还是假设从L开始找R，只不过R的范围是从L+1，到n进行二分，显然每一次的循环的复杂度是logn，但和倍增不同，假设最终答案是r，那么每次倍增的时间复杂度实际上是logn/r，但显然两种解法都需要r次循环，所以二分的循环次数是rlogn，倍增是rlogn-rlogr。

对于本题，倍增还有一个优势是可以保存前面已经做过的部分操作（排序），而二分法判断是否符合条件时就只能快速排序了，复杂度是nlogn，二分法的上限就是O(n(logn)^2)了，但倍增可以达到O(nlogn)。

所以对于倍增来说，普遍是比二分有优势的，但也只是常数上的优势，复杂度量级是一样的。

但在有些特殊的题目里面，由于倍增单向增长的特点，可以用来保存一些信息，进而优化解题的速度。

至于遇到这种东西看不看得出来，就看个人的经验和熟练度了。