每个测试文件均包含多组测试数据。第一行输入一个整数
代表数据组数,每组测试数据描述如下:
第一行输入两个整数
代表数组长度、你需要取出的元素数量。
第二行输入
个整数
代表数组元素。
除此之外,保证单个测试文件的
之和不超过
。
对于每一组测试数据,如果存在至少一种方案,使得最终得到的数组是个严格递增或严格递减数组,在单独的一行上输出
;否则,直接输出
。
4 5 5 1 2 3 4 5 3 2 9 2 4 6 3 12 3 8 7 6 5 5 3 1 3 2 4 5
YES YES YES NO
对于第一组测试数据,不需要进行任何操作,数组已经是严格递增数组。
对于第二组测试数据,选择区间
,随后将这两个元素插入到
之前,得到
。
对于第三组测试数据,符合要求的方案为,选择区间
,随后将剩余的元素重新排列得到
,随后将这三个元素插入到
之后,得到
。
def is_up_or_down(s): up = sorted(s) down = sorted(s,reverse=True) if up == s: return 1#up elif down == s: return 2#down else: return False #s1 is up def is_have_up(s1,s2): s2.sort() for i in range(len(s2)+1): if i == 0: if s1[-1] < s2[i]: return True elif i == len(s2): if s1[0] > s2[i-1]: return True else: if s2[i-1] < s1[0] and s1[-1] <s2[i]: return True return False def is_have_down(s1,s2): s2.sort(reverse = True) for i in range(len(s2)+1): if i == 0: if s1[-1] > s2[i]: return True elif i == len(s2): if s1[0] < s2[i-1]: return True else: if s2[i-1] > s1[0] and s1[-1] > s2[i]: return True return False def have_solution(s,m): if len(s) == m: if is_up_or_down(s): return 'YES' else: return 'NO' i = 0 while i + m <= len(s): s_tichu = s[i:i + m] s_shenxia = s[:i] + s[i + m:] if is_up_or_down(s_tichu): if is_up_or_down(s_tichu) == 1: if is_have_up(s_tichu, s_shenxia): return 'YES' elif is_up_or_down(s_tichu) == 2: if is_have_down(s_tichu, s_shenxia): return 'YES' i += 1 return 'NO' n = int(input()) for k in range(n): a,b = map(int,input().split()) shuzhu = list(map(int,input().split())) print(have_solution(shuzhu,b)) #有超时,力竭