倍增算法总结（含RMQ模板）

部分题目来自《算法竞赛设计进阶》

问题

给定一个长度为n的数列A，有m个询问，每次给定一个整数T，求出最大的k，满足a[1]，a[2]……a[k]的和小于等于T（不会打sigma）

第一反应是二分，这个时候的复杂度是logn

还有第二种解法，用倍增的思想，复杂度为logk（所求答案）。显然倍增要好很多。我讲讲倍增。

如果是暴力的话显然是从前往后一个一个枚举来计算。这里每次只往后移了一格，我们能不能一下子移很多格呢？

当然可以，我们可以用倍增的思想，第一次移1格，第二次移2格……如果再移就超过答案，就把移的格数除以2。如果最后移的格数是0，那么这一格就是答案

#include<cstdio>

#include<cctype>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN =  + ;

int a[MAXN], s[MAXN], n, m, sum;

void read(int& x)

{

    int f = ; x = ; char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -; ch = getchar(); }

    while(isdigit(ch)) { x = x *  + ch - ''; ch = getchar(); }

    x *= f;

}

int main()

{

    read(n); read(m);

    _for(i, , n) read(a[i]), s[i] = s[i-] + a[i];

    while(m--)

    {

        int T; read(T);

        int k = , p = , sum = ; //k为当前在哪一格，p为下一步要移多少格，sum为已经走了的格的总和

        while(p)

        {

            if(k + p <= n && sum + s[k + p] - s[k] <= T)

            {

                sum += s[k + p] - s[k];

                k += p;

                p <<= ;

            }

            else p >>= ;

        }

        printf("%d\n", k);

    }

    return ;

}

hihocoder#1384

发现倍增的套路和二分有点像。出题就出来判断区间是否合法上

这里值得一提的是可以把新加进入的数组sort一遍，然后和之前已经

有序的数组做一次归并，而不用从头再来sort

//这个程序WA，目前还不知道为什么

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cmath>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int n, m, a[MAXN];

int b[MAXN], t[MAXN];

ll T;

inline void read(int& x)

{

	int f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

inline void readll(ll& x)

{

	ll f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

void merge_sort(int L, int R, int p)

{

	_for(i, R + 1, R + p) b[i] = a[i];

	sort(b + R + 1, b + R + p + 1);

	int i = L, pos = L, j = R + 1;

	while(i <= R || j <= R + p)

	{

		if(j > R + p || i <= R && a[i] < b[j]) t[pos++] = a[i++];

		else t[pos++] = b[j++];

	}

	_for(i, L, R + p) a[i] = t[i];

}

bool check(int L, int R, int p)

{

	merge_sort(L, R, p);

	ll res = 0;

	int l = L, r = R + p, tmp = m;

	while(tmp--)

	{

		if(l >= r) break;

		res += (a[r] - a[l]) * (a[r] - a[l]);

		if(res > T) return false;

		r--; l++;

	}

	return true;

}

int main()

{

	int t; read(t);

	while(t--)

	{

		read(n); read(m); readll(T);

		_for(i, 1, n) read(a[i]);

		int L = 1, R, ans = 0, p;

		while(L <= n)

		{

			R = L; p = 1;

			ans++;

	   		while(p)

	   		{

	   	   		if(R + p <= n && check(L, R, p)) //

	   	   		{

	   	   	   		R += p;

			   		p <<= 1;

		   		}

		   		else p >>= 1;

	   		}

	   		L = R + 1;

		}

		printf("%d\n", ans);

	}

	return 0;

}

RMQ算法模板 poj 3264（快速求区间最值，不支持修改）

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 8e4;

const int MAXM = 30;

int dmin[MAXN][MAXM], dmax[MAXN][MAXM], a[MAXN], n, q;

void RMQ_init()

{

	_for(i, 1, n) dmin[i][0] = dmax[i][0] = a[i];

	for(int j = 1; (1 << j) <= n; j++)

		for(int i = 1; i + (1 << j) - 1 <= n; i++)

		{

			dmax[i][j] = max(dmax[i][j-1], dmax[i + (1 << (j-1))][j-1]);

			dmin[i][j] = min(dmin[i][j-1], dmin[i + (1 << (j-1))][j-1]);

		}

}

int RMQ_ans(int l, int r)

{

	int k = 0;

	while((1 << (k + 1)) <= r - l + 1) k++;

	return max(dmax[l][k], dmax[r - (1 << k) + 1][k]) - min(dmin[l][k], dmin[r - (1 << k) + 1][k]);

}

int main()

{

	scanf("%d%d", &n, &q);

	_for(i, 1, n) scanf("%d", &a[i]);

	RMQ_init();

	while(q--)

	{

		int l, r;

		scanf("%d%d", &l, &r);

		printf("%d\n", RMQ_ans(l, r));

	}

	return 0;

}

巴特西

倍增算法总结（含RMQ模板）

最新文章

热门文章

巴特西

倍增算法总结 （ 含RMQ模板）

最新文章

热门文章

倍增算法总结（含RMQ模板）