首页 > 试题广场 >

重排数列

[编程题]重排数列
  • 热度指数:147 时间限制: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
这道题可以这么理解,相邻的两个元素相乘能被4整除,那么至少相邻的两个元素的各自因数中,相乘要有4
那么可以把一个数看成因数有4,或者因数只有2,或者因数只有1
比如6可以看成因数有2,8可以看成因数有4,9的话因数就只有1
那么就总共3种情况,用一个字典dit记录对应因数出现的次数,分别为dit[0],dit[1],dit[2],表示因数只有1,因数只有2,因数含有4

那么分析一下具体情况,能够相乘因数有4,对于一个数的因数是1的时候,它只能和因数是4的数相乘才能满足条件即:1*4,而因数为2的情况只要不和因数为1的数配对则成立,所以我们只需要重点关注因数为1的情况

那么假设i个因数为1的数,
①只有因数1和因数4的数情况下,i-1个因数为4的数来配对,例如1*4*1*4*1
②如果有因数为2的情况,显然因数为2的数不能接在1后面,那么则需要i个因数为4的数来配对。例如1*4*1*4*1*4*2*2

所以dit[1] == 0的情况,按照①中的计算,dit[0]>dit[2]-1则输出No
dit[1]!=0的情况,按照②中的计算,dit[0]>dit[2]则输出No
其他情况并不需要判断,输出Yes即可

import sys
t =int(sys.stdin.readline().strip())
while t>0:
    t-=1
    dit ={0:0,1:0,2:0}
    n =int(sys.stdin.readline().strip())
    lit =list(map(int,(sys.stdin.readline().strip().split(" "))))
    for i inrange(len(lit)):
        if lit[i]%4==0:
            dit[2] +=1
        elif lit[i]%2==0:
            dit[1] +=1
        else:
            dit[0] +=1
    if dit[1]==0anddit[0]>dit[2]+1:
        print("No")
        continue
    if dit[1]!=0anddit[0]>dit[2]:
        print("No")
        continue
    print("Yes")
    continue



编辑于 2020-08-08 01:12:09 回复(0)