1.P1816 忠诚
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入输出格式
输入格式：
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式：
输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入样例#1：
10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10
输出样例#1：
2 3 1
(*^__^*) 嘻嘻…… 代码：
1.AC代码——线段树做法
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int N = 100003; 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<=m; i++) { scanf("%d%d",&a,&b); ans=0x7fffffff; ask(1); printf("%d ",ans); } return 0; }
2.RMQ做法（会W掉一个点）
#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<=15; 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 2 7 8 1 4 3 2
输出样例#1：
0 7 7 1 1 3
说明
【数据规模】
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 "); q[1]=1; for(int i=2; i<=n; i++) { printf("%d ",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 ",ans); } return 0; }
自己选的路，跪着也要走完！！！