首页 > 代码库 > 58. 延绵的山峰
58. 延绵的山峰
58. 延绵的山峰
★★☆ 输入文件：climb.in 输出文件：climb.out 简单对比
时间限制：1 s 内存限制：512 MB
问题描述
有一座延绵不断、跌宕起伏的山，最低处海拔为0，最高处海拔不超过8848米，从这座山的一端走到另一端的过程中，每走1米海拔就升高或降低1米。有Q个登山队计划在这座山的不同区段登山，当他们攀到各自区段的最高峰时，就会插上队旗。请你写一个程序找出他们插旗的高度。
输入文件
第1行，一个整数N(N<=10^6)，表示山两端的跨度。
接下来N+1行，每行一个非负整数Hi，表示该位置的海拔高度，其中H0=Hn=0。
然后是一个正整数Q(Q<=7000)，表示登山队的数量。
接下来Q行，每行两个数Ai, Bi，表示第i个登山队攀爬的区段[Ai,Bi]，其中0<=Ai<=Bi<=N。
输出文件
Q行，每行为一个整数，表示第i个登山队插旗的高度。
样例输入
10
0
1
2
3
2
3
4
3
2
1
0
5
0 10
2 4
3 7
7 9
8 8
样例输出
4
3
4
3
2
[1,n]
//RMQ裸题 #include<cstdio>#include<iostream>using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int N=1e6+5;int n,m,p[21],l[N],f[N][21];void pre_deal(){ for(int i=0;i<=20;i++){ p[i]=1<<i; if(p[i]<=n) l[p[i]]=i; } for(int i=2,near;i<=n;i++){ if(l[i]) near=l[i]; else l[i]=near; }}void RMQ(){ for(int j=1;j<=20;j++){ for(int i=1;i+p[j]-1<=n;i++){ f[i][j]=max(f[i][j-1],f[i+p[j-1]][j-1]); } }}int query(int i,int j){ int k=l[j-i+1]; return max(f[i][k],f[j-p[k]+1][k]);}int main(){ freopen("climb.in","r",stdin); freopen("climb.out","w",stdout); n=read(); for(int i=0;i<=n;i++) f[i][0]=read(); pre_deal(); RMQ(); m=read(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); if(!x&&!y){puts("0");continue;} if(!x) ++x; printf("%d\n",query(x,y)); } return 0;}
[0,n]
//RMQ裸题 #include<cstdio>#include<iostream>using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int N=1e6+5;int n,m,p[21],l[N],f[N][21];void pre_deal(){ for(int i=0;i<=20;i++){ p[i]=1<<i; if(p[i]<=n) l[p[i]]=i; } for(int i=2,near;i<=n+1;i++){//1W:10-0+1==11,so n+1 if(l[i]) near=l[i]; else l[i]=near; }}void RMQ(){ for(int j=1;j<=20;j++){ for(int i=0;i+p[j]-1<=n;i++){ f[i][j]=max(f[i][j-1],f[i+p[j-1]][j-1]); } }}int query(int i,int j){ int k=l[j-i+1]; return max(f[i][k],f[j-p[k]+1][k]);}int main(){ freopen("climb.in","r",stdin); freopen("climb.out","w",stdout); n=read(); for(int i=0;i<=n;i++) f[i][0]=read(); pre_deal(); RMQ(); m=read(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); printf("%d\n",query(x,y)); } return 0;}
58. 延绵的山峰
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。