洛谷 1440 求m区间内的最小值

时间：2022-06-24 14:51:59

　　　　　　　　　　　　洛谷  1440　求m区间内的最小值

题目描述

一个含有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

最后祝大家，大吉大利，今晚吃鸡啊哈。

一世安宁

相关文章