P3647.第1题-tk的强迫症
题目内容
给定一个长度为 n 的整数数组 {a1,a2,...,an}；
由于 Tk 的 强追症，他不希望数组中同时存在奇数和偶数。为了满足条件，可以对数组执行以下操作，一次操作描述为：
- 选择两个相邻元素 ai 和 ai+1 ，将它们从数组中删除，并在原位置插入它们的乘积 ai×ai+1 。
求解，使数组仅包含奇数或仅包含偶数，所需的最少操作次数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) ，表示数据组数;此后每组测试数据格式如下：
第一行输入一个整数 n(1≦n≦2×105) ，表示数组的长度；
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) 表示数组元素。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每组测试数据，新一行输计一个整数，表示使数组仅包含奇数或仅包含偶数所需的最少操作次数。
样例1
输入
2
2
1 2
3
2 3 2
输出
1
1
说明
在第一个样例中，n=2 ，数组 {1,2 }；对这两个元素进行一次操作，得到 1×2=2 ，数组变为 {2}，仅含偶数，故答案为 1 。
在第二个样例中，n=3 ，数组 {2,3,2 }；只需一次操作如合并后两个元素 3 和 2 得到 6 ，数组变为 {2,6}，仅含偶数，故答案为 1 。
