题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
题解：
偷偷告诉你，我超级喜欢暴力的。所以看到这个题的第一反应，就是打暴力
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[],n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
cout<<<<endl;
for(int i=;i<=n;i++){
int s=i-m,minn=;
if(s<)
s=;
for(int j=s;j<i;j++)
minn=min(minn,a[j]);
cout<<minn<<endl;
}
return ;
}
hhh，没想到，居然有50分；
next，我还是想不出正解，因为那时候刚学队列然而我对队列无感，对于讲队列的学长更是，emmm。在这里吐槽一句，他的代码实在是太丑了。
然后，我就开始想方设法，为所欲为的给它提速，然后加了一个特判
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[],n,m,minn=,minp;
int main(){
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
cout<<<<endl;
for(int i=; i<=n; i++){
int s=i-m;
if(s<) s=;
if(a[i-]<=minn) minn=a[i-],minp=i-;
if(minp<s){
minn=a[s],minp=s;
for(int j=s; j<i; j++)
if(a[j]<=minn)
minn=a[j],minp=j;
}
cout<<minn<<endl;
}
return ;
}
然后，居然70了，哇，amazing。
最后呢，听一位学长说，cout输出‘\n’比printf或者输出endl快，就试了一哈子。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[],n,m,minn=,minp;
int main(){
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
cout<<<<endl;
for(int i=; i<=n; i++){
int s=i-m;
if(s<) s=;
if(a[i-]<=minn) minn=a[i-],minp=i-;
if(minp<s){
minn=a[s],minp=s;
for(int j=s; j<i; j++)
if(a[j]<=minn)
minn=a[j],minp=j;
}
cout<<minn<<"\n";
}
return ;
}
这样居然A了，简直了。
不过呢，还是要尊重正解。
#include<complex>
#include<cstdio>
using namespace std;
const int N=2e6+;
int n,m,head=,tail,a[N],q[N];
int main() {
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
q[++tail]=;
printf("0\n");
for(int i=; i<=n; i++) {
printf("%d\n",a[q[head]]);
if(q[head]<=i-m)head++;
while(head<=tail && a[q[tail]]>=a[i])
tail--;
q[++tail]=i;
}
return ;
}
正解是队列。
题目说完了，进入吐槽时间。
吐槽：
讲队列的那位学长真的是，我第一次听他讲课的时候还没有感觉他长的那么惨无人道，惨绝人寰。现在真是越看越，emmm。话说他给我们布置的题目，说是用队列做的，我全没用队列，全用的暴力诶，哎也不是不想写队列，emmm，不会啊，现在更是好久没复习队列了，感觉队列和栈都快分不清楚了。哎，看来我有必要继续颓废了。hhh
最后祝大家，大吉大利，今晚吃鸡啊哈。
一世安宁