ZJNU 1365 - Window--中级
标签：窗户 说明 观察 printf div return 答案 相同 col
每次都寻找长度为k的区间内的最小值显然很容易超出时间限制
所以可以把窗户看作一个数量固定的队列
每次观察入列与出列的元素对答案贡献如何，以更新答案
1 /*
2 Written By StelaYuri
3 */
4 #include 5 int tmp[1000010],max[1000010];
6 int gmax(int i,int k)
7 {
8 int j,m=tmp[i];
9 for(j=i-1;j>i-k;j--)
10 if(mtmp[j])
11 m=tmp[j];
12 return m;
13 }
14 int gmin(int i,int k)
15 {
16 int j,m=tmp[i];
17 for(j=i-1;j>i-k;j--)
18 if(m>tmp[j])
19 m=tmp[j];
20 return m;
21 }
22 int main()
23 {
24 int n,k,i,lmin,lmax;
25 scanf("%d%d",&n,&k);
26 for(i=0;i)
27 scanf("%d",&tmp[i]);
28 lmin=gmin(k-1,k);
29 lmax=gmax(k-1,k);
30 printf("%d",lmin);
31 max[0]=lmax;
32 for(;i)
33 {
34 scanf("%d",&tmp[i]);
35 if(tmp[i-k]==lmin)//如果即将移出的数字与前一位置的答案相同，说明答案需要重新查找
36 lmin=gmin(i,k);
37 else if(tmp[i]//如果即将移入的数字比前面的答案小，更新答案为当前位置输入的答案
38 lmin=tmp[i];
39 printf(" %d",lmin);
40 if(tmp[i-k]==lmax)
41 lmax=gmax(i,k);
42 else if(tmp[i]>lmax)
43 lmax=tmp[i];
44 max[i+1-k]=lmax;
45 }
46 printf("\n%d",max[0]);
47 for(i=1;i1;i++)
48 printf(" %d",max[i]);
49
50 return 0;
51 }
ZJNU 1365 - Window--中级
标签：窗户 说明 观察 printf div return 答案 相同 col
原文地址：https://www.cnblogs.com/stelayuri/p/12234995.html
评论