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
当时看着标签是dp才做的，结果发现是一个数据结构体qwq
那就来复习一下数据结构吧
区间最值，很容易想到一下几种思路:
线段树，树状数组，st表
我自己的方法是线段树，AC代码如下（很简单的板子）
#include<bits/stdc++.h> using namespace std; int a[502000],t[502000]; int n,m; void build(int p,int l,int r) { if(l==r) { t[p]=a[l]; return; } int mid=(l+r)/2; build(2*p,l,mid); build(2*p+1,mid+1,r); t[p]=min(t[2*p],t[2*p+1]); } int find(int x,int y,int l,int r,int p) { if(x<=l&&y>=r) { return t[p]; } int mid=(l+r)/2; int a=9999999,b=9999999; if(x<=mid) a=find(x,y,l,mid,2*p); if(y>mid) b=find(x,y,mid+1,r,2*p+1); return min(a,b); } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); while(m--) { int x,y; cin>>x>>y; cout<<find(x,y,1,n,1)<<" "; } return 0; }
题解中的其他方法：
树状数组：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[1000001]; int tree[1000001]; int n,m; int lowbit(int x) { return x&(-x); } void update(int x,int v) { while(x<=n) { if(tree[x]>v) tree[x]=v; else return; x+=lowbit(x); } } int getmin(int x,int y) { int now=y; int maxl=2147483647; while(now>=x) { if(now-lowbit(now)>x) { maxl=min(maxl,tree[now]); now-=lowbit(now); } else { maxl=min(maxl,a[now]); --now; } } return maxl; } int main() { memset(tree,127,sizeof(tree)); cin>>n>>m; int x,y; //n++; for(int i=1;i<=n;++i) { cin>>a[i]; update(i,a[i]); } for(;m>0;--m) { cin>>x>>y; cout<<getmin(x,y)<<' '; } return 0; }
st表：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int a[100005][20],m,n; inline int getint() //读入优化 { int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')f=1,x=getchar(); while(x>='0'&&x<='9') {a=a*10+x-'0';x=getchar();} return f?-a:a; } void rmq_st(int n) //预处理，st表 { for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) //思考为什么外循环j套i，而不是外循环i套j if(i+(1<<j)-1<=n) a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1]); //原因在于每个区间更新都是由1个点开始慢慢增加区间范围 } int main() { m=getint();n=getint(); for(int i=1;i<=m;i++)a[i][0]=getint(); //读入数据，对于每个点开始时最小值就是它本身 rmq_st(m); while(n--) { int l=getint(),r=getint(),k=log2(r-l+1); printf("%d ",min(a[l][k],a[r-(1<<k)+1][k])); //查询时注意思路 } return 0; }
还有一种不知道是什么神奇方法的方法（看着像是一种贪心？）
#include<bits/stdc++.h> using namespace std; struct fff{ int x,y; }; fff a[100001]; bool cmp(fff l,fff v){ return l.x<v.x; } int main(){ int m,n,t,k; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++){ scanf("%d",&a[i].x); a[i].y=i; //为每个账目编号； } sort(a+1,a+1+m,cmp); for(int i=1;i<=n;i++){ scanf("%d%d",&t,&k); for(int j=1;j<=m;j++){ if(a[j].y>=t&&a[j].y<=k){ printf("%d ",a[j].x); break; //一个小优化； } } } return 0; } //主要是快排，先把账目排一遍，再找提问范围里靠前的，找到后就输出；（比较好理解）