http://www.cnblogs.com/cnjy/archive/2009/08/30/1556566.html
RMQ(Range Minimum/Maximum Query)问题:
RMQ问题是求给定区间中的最值问题。当然,最简单的算法是O(n)的,但是对于查询次数很多(设置多大100万次),O(n)的算法效率不够。可以用线段树将算法优化到O(logn)(在线段树中保存线段的最值)。不过,Sparse_Table算法才是最好的:它可以在O(nlogn)的预处理以后实现O(1)的查询效率。
下面把Sparse Table算法分成预处理和查询两部分来说明(以求最小值为例)。
预处理:
预处理使用DP的思想,f(i, j)表示[i, i+2^j - 1]区间中的最小值,我们可以开辟一个数组专门来保存f(i,
j)的值。
例如,f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值
注意, 因为f(i, j)=[i, i+2^j - 1]可以由f(i,
j - 1)和f(i+2^(j-1), j-1)导出
f(i, j - 1)表示的是[i,i+2^(j-1)-1];
f(i+2^(j-1), j-1)表示的是[i+2^(j-1),i+2^(j-1)+2^(j-1)-1]=[i+2^(j-1),i+2^j-1]导出,
总区间为:[i,i+2^(j-1)-1];
而递推的初值(所有的f(i, 0) = i)都是已知的
所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。
查询:
假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <(n - m + 1).
于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];
而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值
我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.
例如, rmq(0, 11) = min(f(0, 3), f(4, 3))
由此我们要注意的是预处理f(i,j)中的j值只需要计算log(n+1)/log(2)即可,而i值我们也只需要计算到n-2^k+1即可。
/* hdoj 3486 RMQ 具体细节 */ #include<iostream> #include<stdio.h> #include<math.h> #include<string.h> using namespace std; #define N 200010 int dp[N][20],a[N],n; void init() { int i,j,limit; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) dp[i][0]=a[i]; //从第i个开始2^j个数 for(j=1;j<=log((double)(n+1))/log(2.0);j++) { limit=n+1-(1<<j); for(i=1;i<=limit;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } } int query(int a,int b)//a,b区间 { int k=(int)(log((double)(b-a+1))/log(2.0)); return max(dp[a][k],dp[b-(1<<k)+1][k]); } int get(int m)//求分成m段情况下,最大能力和 { int i,len,sum=0; len=n/m;//每段的长度,一段一段的查找 for(i=1;i<=m;i++) { sum+=query(len*(i-1)+1,len*i); } return sum; } int main() { int k,i,j,sum,maxn,minn,left,right,mid,t,ans; //freopen("test.txt","r",stdin); while(scanf("%d%d",&n,&k)) { if(n<0&&k<0) break; maxn=-1;minn=99999999;sum=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; if(a[i]>maxn) maxn=a[i]; if(a[i]<minn) minn=a[i]; } minn=minn!=0?minn:1; maxn=maxn?maxn:1; if(maxn>=k) {//最大的值大于k,只需招一个人,分1段 printf("1\n"); continue; } if(sum<k)//总和小于k,无法满足 { printf("-1\n"); continue; } init(); right=min((k/minn+1),n); left=k/maxn;//区间 while(left<=right)//二分枚举 段数 { mid=(left+right)/2; t=get(mid); if(t>k) { right=mid-1; ans=mid; } else left=mid+1; } printf("%d\n",ans); } return 0; }