Ikari_Shinji @ 2019-01-18 21:51:24
50分,测评情况:
#include<cstdio>
#define min(a,b) (a<b?a:b)
const int N=2000005;
int n,m,a[N],ans[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
ans[0]=0;
ans[1]=a[0];
for(int i=2;i<n;i++){
int num=2147483647;
for(int j=1;j<=m;j++){
if(i-j<0) break;
else num=min(num,a[i-j]);
}
ans[i]=num;
}
for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
return 0;
}
by SSerxhs @ 2019-01-18 21:53:03
复杂度都不对就洗洗睡吧
by 周子衡 @ 2019-01-18 21:54:50
单调队列题
by Kevin_Wa @ 2019-01-18 21:56:49
线段树
by 周子衡 @ 2019-01-18 22:00:48
暴力显然是
我们可以构造一个队列,保存所有可能成为正确答案的元素
顺序扫描每一个元素,可以发现:如果
每次如果最先进入队列的元素过期了,也把它踢出
可以发现,这个队列的元素单调递增,故称单调队列
我讲得可能不是很清楚,具体看题解和日报吧
可以用
by 周子衡 @ 2019-01-18 22:01:15
时间复杂度