求m区间的最小值

代码1；（手写单调队列）

#include<iostream>
using namespace std;
#define N 2000005
int n,m,a[N],b[N];
int head=0,rear=0;
int main(){
	scanf("%d %d",&n,&m);
	scanf("%d",&a[1]);
	printf("0\n");
	b[rear]=1;
	for(int i=2;i<=n;i++){
		scanf("%d",&a[i]);
		//注意队列为空的判断条件，如果初始化时head=0,rear=1:则当head<rear的时候队列不为空
		//当head==rear=0,则队列head<=rear的时候不为空
		//这里b[head]<i-m而不是小于等于i-m,是因为它求的是第i个数的前m个数中的最小值
		while(head<=rear&&b[head]<i-m){
			head++;
		}
		printf("%d\n",a[b[head]]);
		while(head<=rear&&a[b[rear]]>a[i]){
			rear--;
		}
		b[++rear]=i;
	}
	return 0;

}

代码2（STL单调队列）：

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,a[N],b[N];
deque<int> q;
//快读函数：
//设置一个变量用于标记数的正负，一个变量用来记录数的大小
inline int read(){
    char a;
    int f=1,x=0;
    a=getchar();
    //先读入数据的符号，如果是负号，就将f变为-1
    while(a<='0'||a>='9'){
        if(a=='-'){
            f=-1;
        }
        a=getchar();
    }
    //读入数据
    while(a>='0'&&a<='9'){
        x=x*10+a-'0';
        a=getchar();
    }
    return x*f;
}
int main(){
    n=read();m=read();
    b[0]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
       while(!q.empty()&&a[q.back()]>a[i]){
        q.pop_back();
       }
       q.push_back(i);
       while(!q.empty()&&q.front()<=i-m){
        q.pop_front();
       }
       b[i]=a[q.front()];
    }
    for(int i=0;i<n;i++){
        printf("%d\n",b[i]);
    }
    return 0;
}
//快写函数：如果数大于10，就一位一位输出，用递归调用
//如果是小于10的数，则输出对应的字符
//void write(int x){
//	if(x>10) write(x/10);
//	putchar(x%10+'0');
//}

注意点：

1.一定要注意题目的输出的格式

2.本题目是求第i个数的前m个数中的最小值（不包括第i个数）

读写速度差异比较：

1.cin cout最慢

2.ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)与scanf和printf差不多，但是还是慢与scanf和printf

3.printf与scanf与前两者都快

4.快写函数和快读函数比3快(以字符串的形式)，getchar ()和putchar()

快读函数：

inline int read(){
    char a;
    int f=1,x=0;
    a=getchar();
    //先读入数据的符号，如果是负号，就将f变为-1
    while(a<='0'||a>='9'){
        if(a=='-'){
            f=-1;
        }
        a=getchar();
    }
    //读入数据
    while(a>='0'&&a<='9'){
        x=x*10+a-'0';
        a=getchar();
    }
    return x*f;
}

快写函数：

void write(int x){
	if(x>10) write(x/10);
	putchar(x%10+'0');
}