T1.题目描述
有一个很长的花坛,一部分地块已经种植了花,另一部分没有种植花。花不能种植在相邻的地块上,否则它们会争夺水源,两者都会死去。
给你一个整数数组 a 表示花坛,由若干 0 和 1 组成,其中 0 表示空地、1 表示已种植的花。再给定一个整数 k,表示希望种植的花的数量。问是否可以在不违反种植规则的情况下种入 k 朵花?
输入格式
第一行包含一个整数 t,表示测试数据的组数。
对于每组测试数据:
第一行包含一个整数 n,表示花坛的长度。
第二行包含 n 个整数 a[i],其中每个整数为 0 或 1。
第三行包含一个整数 k,表示希望种植的花的数量。
输出格式
对于每组测试数据,输出 Yes 或 No,表示是否可以在不违反规则的情况下种入 k 朵花。
输入输出样例
输出
说明/提示
样例解释 1
第一组数据:可以在 a[3] 位置种植一朵花,满足 k=1 的要求,因此输出 Yes。
第二组数据:无法在不违反规则的情况下种植两朵花,最多只能种植一朵,因此输出 No。
第三组数据:可以在 a[1]、a[3] 和 a[5] 位置种植三朵花,满足 k=3 的需求,因此输出 Yes。
数据范围
测试点 t n k 1∼20 1≤t≤100 1≤n≤2×10 0≤k≤n
a[i] 为 0 或 1
a 中不存在相邻的两朵花