往届 ACM 队训练题 (参考)

1103. sunny的队列

单点时限: 2.0 sec

内存限制: 256 MB

ecnu 超市的结账处排了很长很长的队列,队列有 N(1<=N<=100000) 个人,标号分别为 1…N。由于等待了很长时间。所以顾客们都很不开心。所以每个人都有一个不开心数值 value( -1000<=value<=1000 ), 为了调节气氛,超市经理要 sunny 组织一次抽奖活动。从队列第一个人 (也就是队列左端) 开始,调查以第一个人为左端点的长度为 K(1<=K<=N) 的子队列中人们的不开心数值,然后取这 K 个人中不开心数值最高的人进行奖励。然后从第二个人开始进行调查以其为左端点的长度为 K 的子队列,依次类推,直到调查人数少于 K 则终止活动。

注意同学们都很执着,所以队列中人们的不开心数值不会因为自己或是别人得到了奖励而有任何改变,队列中人们的位置也不会发生任何改变。

比如 N=8 的队列 [1 3 -1 -3 5 3 6 7]

则活动进行了 6 次调查,分别为

queue Max value

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

[] 内表示被调查的人

为了方便准备奖品,sunny 请你帮忙写个程序,输出每次调查中被奖励人的不开心数值

输入格式

第一个整数为 T, 表示有 T 组测试数据

每组测试数据第一行有两个整数 N,K;

第二行是 N 个以空格间隔的整数 value[1],value[2],value[3]…value[N],表示队列中从左往右人们的不开心数值

value[1] 表示队列第一个人的不开心数值

输出格式

对于每组测试数据输出一行,输出每次调查中被奖励人的不开心数值 (按从左往右的调查顺序), 数值之间间隔一个空格,第一个数据前没有空格最后一个数据后输出换行

样例

Input
1
8 3
1 3 -1 -3 5 3 6 7
Output
3 3 5 5 6 7
不限期开放

题目列表