体验RMQ

来源:转载

二维数组里找未知方阵的最大最小值之差。  

刚拿到这个题时感觉压力很大,因为虽然遍历扫描可以解决,但n^3的复杂度很大可能过不了,即使过了也丧失这道题的意义。于是用到了RMQ算法,强大的预处理,为什么呢:1,因为测试数据的数目不定,可能很大,如果只是简单的递归寻找,再寻找每一种情况时候必然会出现大量重复的过程,而这些过程没有被有效的记录下来供后面使用,使得效率不高;2,数据量庞大,我们不能一次扫描,于是在进行计算前对二维数组进行压缩,二叉树式压缩(我是这样看的,很不专业),RMQ最精妙之处就在于遍历到了树的所有末端,而又无任何重复的浪费。

即使思路清晰了,但实现上还是遇到很多问题,看来基本功还有待提升。以下代码,写得较冗长,见谅。

#include<cstdio>#include<iostream>#include<cstdlib>#include<cmath>using namespace std;short M[251][251][9];short F[251][251][9];inline short max4(int a,int b,int c,int d){ int ma; if(max(a,b)>=max(c,d))ma=max(a,b); else ma=max(c,d); return ma;}inline short min4(int a,int b,int c,int d){ int mi; if(min(a,b)<=min(c,d))mi=min(a,b); else mi=min(c,d); return mi;}int main(){ int N; int B; int K; int x; int y; scanf("%d%d%d",&N,&B,&K); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) { scanf("%d",&F[i][j][0]); M[i][j][0]=F[i][j][0]; } for(int n=1; (1<<(n-1))<=B; n++) for(int i=1; i+(1<<n)-1<=N; i++) for(int j=1; j+(1<<n)-1<=N; j++) { F[i][j][n]=max4(F[i][j][n-1], F[i+(1<<(n-1))][j][n-1], F[i][j+(1<<(n-1))][n-1], F[i+(1<<(n-1))][j+(1<<(n-1))][n-1]); M[i][j][n]=min4(M[i][j][n-1], M[i+(1<<(n-1))][j][n-1], M[i][j+(1<<(n-1))][n-1], M[i+(1<<(n-1))][j+(1<<(n-1))][n-1]); } int KK=(int)(log2(B)); for(int i=1; i<=K; i++) { scanf("%d%d",&x,&y); short max=max4(F[x][y][KK], F[x+B-(1<<KK)][y][KK], F[x][y+B-(1<<KK)][KK], F[x+B-(1<<KK)][y+B-(1<<KK)][KK]); short min=min4(M[x][y][KK], M[x+B-(1<<KK)][y][KK], M[x][y+B-(1<<KK)][KK], M[x+B-(1<<KK)][y+B-(1<<KK)][KK]); printf("%d/n",(max-min)); } system("pause"); return 0;}

总结:1,大数组(特别是多维)应该在main以外定义,否则系统承受不了;
     2,发现将cin/cout改写为scanf/printf后速度提升相当大,直接从700ms降到188ms;


分享给朋友:
您可能感兴趣的文章:
随机阅读: