题目描述

小易有一个长度为N的正整数数列A = {A[1], A[2], A[3]..., A[N]}。牛博士给小易出了一个难题:对数列A进行重新排列,使数列A满足所有的A[i] * A[i + 1](1 ≤ i ≤ N - 1)都是4的倍数。小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。

输入描述

输入的第一行为数列的个数t(1 ≤ t ≤ 10),

接下来每两行描述一个数列A,第一行为数列长度n(1 ≤ n ≤ 10^5）

第二行为n个正整数A[i](1 ≤ A[i] ≤ 10^9)

输出描述

对于每个数列输出一行表示是否可以满足牛博士的要求，如果可以输出Yes，否则输出No。

思路：

记录能被4整除的个数和能被2整除的个数以及奇数的个数，然后分情况讨论。

Java代码

import java.util.Scanner;public class RearrangeSequence {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        while (sc.hasNext()) {            int t = sc.nextInt();            for (int i = 0; i < t; i++) {                int n = sc.nextInt();                //表示4的倍数的个数                int cnt4 = 0;                //表示2的倍数的个数                int cnt2 = 0;                //表示其他数                int cnt1 = 0;                for (int j = 0; j < n; j++) {                    int x = sc.nextInt();                    if (x % 4 == 0) {                        cnt4++;                    } else if (x % 2 == 0) {                        cnt2++;                    } else {                        cnt1++;                    }                }                if (cnt2 == 0) {                    if (cnt4 >= cnt1 - 1) {                        System.out.println("Yes");                    } else {                        System.out.println("No");                    }                } else {                    if (cnt4 >= cnt1) {                        System.out.println("Yes");                    } else {                        System.out.println("No");                    }                }            }        }    }}