首页 > 试题广场 >

重排数列

[编程题]重排数列
  • 热度指数:96 时间限制: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

输入

2
3
1 10 100
4
1 2 3 4

输出

Yes
No
设置一个计数器,循环遍历数组中的每个元素,对于元素A[i],如果该元素可以被4整除,则count+2, 如果只可以被2整除不可以被4整除,则count+1.
遍历完数组,判断count值是否大于等于数组的长度n,如果是,则该数列可以重排之后满足牛博士的要求,否则不能满足要求
发表于 2018-05-27 15:22:57 回复(0)
while True:
    try:
        t=int(raw_input().strip())
        for i in range(t):
            n=int(raw_input().strip())
            a=list(map(int,raw_input().strip().split()))
            count4,count2,countodd=0,0,0
            for j in a:
                if j%4==0:
                    count4+=1
                else:
                    if j%4==2:
                        count2+=1
                    else:
                        countodd+=1
            if count2==0:
                if count4>=countodd-1:
                    print('Yes')
                else:
                    print('No')
            else:
                if count4>=countodd:
                    print('Yes')
                else:
                    print('No')
    except:
        break

发表于 2018-07-30 16:35:04 回复(0)