首页 > 代码库 > 洛谷——RMQ
洛谷——RMQ
1.P1816 忠诚
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入输出格式
输入格式：
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式：
输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入样例#1：
10 31 2 3 4 5 6 7 8 9 102 73 91 10
输出样例#1：
2 3 1
(*^__^*) 嘻嘻…… 代码：
1.AC代码——线段树做法
#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int N = 2000003;int m,n,a,b,ans;struct Tree{ int l;int r;int w; }t[4*N];void build(int k,int ll,int rr) { t[k].l=ll,t[k].r=rr; if(ll == rr) { scanf("%d",&t[k].w); return ; } int mid=(ll+rr)/2; build(k*2,ll,mid); build(k*2+1,mid+1,rr); t[k].w=min(t[k*2].w,t[k*2+1].w);}void ask(int k) { if(t[k].l>=a&&t[k].r<=b) { ans=min(ans,t[k].w); return ; } int mid=(t[k].l+t[k].r)/2; if(a<=mid) ask(k*2); if(b>mid) ask(k*2+1);}int main() { scanf("%d%d",&n,&m); build(1,1,n); for(int i=1; i<=n; i++) { a=i-m,b=i-1; if(i==1) { cout<<0<<endl; continue ; } if(a<1) a=1; ans=0x7fffffff; ask(1); printf("%d\n",ans); } return 0;}
2.RMQ做法（会T掉）
#include<iostream>#include<cstdio>using namespace std;const int N = 10003;int n,m,x,y,s[N],q,log[N];int f[N][15],ans[N];int main() { cin>>n>>m; for(int i=1; i<=n; i++) cin>>s[i]; //log2 a = x，表示2的x次方=a for(int i=2; i<=n; i++) log[i]=log[i>>1]+1; //log数组的下标表示 a，log数组中存的是2的多少次方 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) f[i][j]=0x7fffffff; for(int i=1; i<=n; i++) f[i][0]=s[i]; for(int i=1,k=1; i<=log[n]; i++,k*=2) //k为2的i-1次方 for(int j=1; j+k-1<=n; j++) //j+k-1为左半端的最后一个 f[j][i]=min(f[j][i-1],f[j+k][i-1]);//i-1次方是一半 for(int i=1; i<=m; i++) { cin>>x>>y; int len=log[y-x+1]; ans[i]=min(f[x][len],f[y-(1<<len)+1][len]); //1<<len 表示2的len次方 } for(int i=1; i<=m; i++) cout<<ans[i]<<" "; return 0;}
2.P1440 求m区间内的最小值
题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
输入输出样例
输入样例#1：
6 27 8 1 4 3 2
输出样例#1：
077113
说明
【数据规模】
m≤n≤2000000
(*^__^*) 嘻嘻…… 代码：
1.AC代码——单调队列
#include<iostream>#include<cstdio>#include<queue>using namespace std;int q[2000003];int n,m,x,ans,a[2000003];int head=1,tail=1;int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); printf("0\n"); q[1]=1; for(int i=2; i<=n; i++) { printf("%d\n",a[q[head]]); if(q[head] <= i-m) head++; while(a[i] <= a[q[tail]] && head <= tail) tail--; q[++tail] = i; } return 0;}
2.线段树做法—（会T两个点）
#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int N = 2000003;int m,n,a,b,ans;struct Tree{ int l;int r;int w; }t[4*N];void build(int k,int ll,int rr) { t[k].l=ll,t[k].r=rr; if(ll == rr) { scanf("%d",&t[k].w); return ; } int mid=(ll+rr)/2; build(k*2,ll,mid); build(k*2+1,mid+1,rr); t[k].w=min(t[k*2].w,t[k*2+1].w);}void ask(int k) { if(t[k].l>=a&&t[k].r<=b) { ans=min(ans,t[k].w); return ; } int mid=(t[k].l+t[k].r)/2; if(a<=mid) ask(k*2); if(b>mid) ask(k*2+1);}int main() { scanf("%d%d",&n,&m); build(1,1,n); for(int i=1; i<=n; i++) { a=i-m,b=i-1; if(i==1) { cout<<0<<endl; continue ; } if(a<1) a=1; ans=0x7fffffff; ask(1); printf("%d\n",ans); } return 0;}
自己选的路，跪着也要走完！！！
洛谷——RMQ
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。