區間MAX
作法 : DP
實做 RMQ
參考 http://robertanders.pixnet.net/blog/post/27930664
但是仍不是最快的,所以還有待改進
建表O(Nlog2(N)) 查詢O(log2(N))
/*********************************************************/
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int f[500001][21]={0};
int MAX(int x,int y)
{
if(x>y) return x;
else return y;
}
int input()
{
char cha;
int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
main()
{
int n2[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
int a,b,N,M,st,en;
while(scanf("%d",&N)==1)
{
for(a=1;a<=N;a++)
scanf("%d",&f[a][0]);
int lg=(int)(log10(N)/log10(2.0))+1;
for(b=1;b<=lg;b++)
for(a=1;a<=N;a++)
{
if(a+n2[b]/2>N) break;
f[a][b]=MAX(f[a][b-1],f[a+n2[b]/2][b-1]);
}
scanf("%d",&M);
for(a=1;a<=M;a++)
{
scanf("%d %d",&st,&en);
if(st>en)
{
int temp;
temp=st;
st=en;
en=temp;
}
int l=en-st+1,ANS=0,t=0,flag=st;
while(l!=0)
{
if(l%2==1)
{
ANS=MAX(f[flag][t],ANS);
flag+=n2[t];
}
l=l/2;
t++;
}
printf("%d\n",ANS);
}
}
return 0;
}
以下為所有的優化放入的"目前"最終產物
建表O(Nlog(N)) 查詢O(1)
/**********************************************************/
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int f[500001][20];
int MAX(int x,int y)
{
if(x>=y) return x;
else return y;
}
int input()
{
char cha;
int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
int lg2(int num)
{
if(num<2) return 0;
if(num<4) return 1;
if(num<8) return 2;
if(num<16) return 3;
if(num<32) return 4;
if(num<64) return 5;
if(num<128) return 6;
if(num<256) return 7;
if(num<512) return 8;
if(num<1024) return 9;
if(num<2048) return 10;
if(num<4096) return 11;
if(num<8192) return 12;
if(num<16384) return 13;
if(num<32768) return 14;
if(num<65536) return 15;
if(num<131072) return 16;
if(num<262144) return 17;
if(num<524288) return 18;
}
main()
{
int n2[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
int a,b,N,M,st,en;
while(scanf("%d",&N)==1)
{
for(a=1;a<=N;a++)
f[a][0]=input();
int lg=lg2(N);
for(b=0;b<lg;b++,N-=n2[b])
for(a=1;a<=N;a++)
f[a][b+1]=MAX(f[a][b],f[a+n2[b]][b]);
scanf("%d",&M);
int temp,l,k;
for(a=1;a<=M;a++)
{
st=input(),en=input();
if(st>en)
temp=st,st=en,en,en=temp;
l=en-st+1;
k=lg2(l);
printf("%d\n",MAX(f[st][k],f[en-n2[k]+1][k]));
}
}
return 0;
}
以下是用線段樹所做出來的
在此題由於詢問沒有很大
在記憶體小的形況下 速度會++
感謝 liouzhou_101的提供
建表O(N) 詢問O(logN)
/**********************************************************/
#include<stdlib.h>
#include<stdio.h>
int A[500001],tree[1100001];
int MAX (int x,int y)
{
if(x>=y) return x;
else return y;
}
void set_tree(int l,int r,int k)
{
if(l==r) tree[k]=A[l];
else
{
int m=(l+r)/2;
set_tree(l,m,2*k);
set_tree(m+1,r,2*k+1);
tree[k]=MAX(tree[2*k],tree[2*k+1]);
}
}
int get(int l,int r,int k,int x,int y)
{
if(l==x&&r==y) return tree[k];
else
{
int m=(l+r)/2;
if(m>=y) return get(l,m,2*k,x,y);
else if(m<x) return get(m+1,r,2*k+1,x,y);
else return MAX(get(l,m,2*k,x,m),get(m+1,r,2*k+1,m+1,y));
}
}
int input()
{
char cha;
int x=0;
while(cha=getchar())
if(cha!=' '&&cha!='\n') break;
x=cha-48;
while(cha=getchar())
{
if(cha==' '||cha=='\n') break;
x=x*10+cha-48;
}
return x;
}
main()
{
int N,a,x,y,M,t;
while(scanf("%d",&N)==1)
{
for(a=1;a<=N;a++)
A[a]=input();
set_tree(1,N,1);
scanf("%d",&M);
for(a=1;a<=M;a++)
{
x=input(),y=input();
if(x>y) t=x,x=y,y=t;
printf("%d\n",get(1,N,1,x,y));
}
}
return 0;
}
上一篇:切割數字