问题2857--精神控制(mind)

2857: 精神控制(mind)

时间限制: 1 Sec  内存限制: 128 MB
提交: 65  解决: 52
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一个长度为n的整数数组a。包含你在内,总共有n人做操作,选择数组的首位元素或末尾元素并将其删除称为一次操作。
n个人轮流操作之前,你可以控制其余k个人的操作使其按照你的意愿删去开头或是末尾元素(一开始要确定好,一旦操作开始,不能改了)
假设你是第m次操作,你希望做最优选择,求最大的整数x,能保证第m次操作从数组中取出的元素大于或等于x。
请注意,你没有控制的操作会任意选择要删去的元素在首还是尾。

输入

第一行输入数据组数t
对于每组数据,先输入三个整数n,m,k,然后输入n个整数ai

输出

每组数据输出一个整数,即最大的x,每行一个

样例输入 Copy

4
6 4 2
2 9 2 3 8 5
4 4 1
2 13 60 4
4 1 3
1 2 2 1
2 2 0
1 2

样例输出 Copy

8
4
1
1

提示

在第一组数据中,最优策略是令第一次操作删去最后一个元素,而第二次操作删去第一个元素(也就是控制第1个人选开头,第2个人选末尾)
第一次操作会拿走最后一个元素5。在这轮之后,剩下的数组将是[2,9,2,3,8];
第二次操作会拿走第一个元素2。在这轮之后,剩下的数组将是[9,2,3,8];
如果第三次操作任意选择第一个元素9,轮到第四次操作时,剩下的数组将是[2,3,8],你将选择8(最后1个元素);
如果第三次操作任意选择最后一个元素8,那么轮到第四次操作时,剩下的数组将是[9,2,3],而你将选择9(第1个元素)。
因此,这个策略保证最后至少得到8。
在第二组数据中,最优策略是令第1个人选开头,删去第一个元素。然后,在最坏的情况下,第二次操作和第三次操作都会选择首位元素,最后得到4。
【数据规模和约定】
100%数据 1<=m<=n<=3500,  0<=k<=n-1,  1<=ai<=10^9

来源/分类