部分题目来自《算法竞赛设计进阶》
问题
给定一个长度为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;
}