首页 > 试题广场 >

重排数列

[编程题]重排数列

热度指数：331 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 98M，其他语言196M
算法知识视频讲解

小易有一个长度为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。

示例1

输入

输出

Yes
No

算法知识视频讲解

我要一桶浆糊

# 数列个数
nums = int(input())
for i in range(nums):
    # 对每个数列进行处理
    n = int(input())  # 数列长度
    A = list(map(int, input().split(' ')))
    # 思路：统计出奇数、4的倍数、非4的倍数的偶数的个数，分别记为（a,b,c），分情况考虑：
    # 1、a<=b时，YES；2、当a=b+1 and c==0时，YES；3、否则NO
    a = b = c = 0
    for num in A:
        if num % 2 == 1:
            a += 1
        else:
            if num % 4 == 0:
                b += 1
            else:
                c += 1
    # 判断
    if a <= b:
        print('Yes')
    elif a == b + 1 and c == 0:
        print('Yes')
    else:
        print('No')

发表于 2018-08-07 16:20:43 回复(1)