首页 > 试题广场 >

重排数列

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

数学

这个题要不是看左神讲过,可太难想了。主要思路是统计三种数:(1) 能被4整除,记为4;(2) 能被2整除,记为2;(3) 其他,能被1整除的数,记为1。
1)如果没有2,1和4交替排列即可,但是1的数量不能超过4的数量+1,否则4不够插空,会有连续的1,而连续的1出现会使得A[i]*A[i+1]不是4的倍数。
2)如果有2,同样也要满足1的数量不超过4的数量+1,如果1和4的数量相等,能凑出“1 4 1 4 1 4”,这种情况下,需要有偶数个2,得到“1 4 1 4 1 4 2 2 2 2”,否则2没有办法配对也会无法满足题设。如果1比4多一个,能凑出“1 4 1 4 1 4 1”,仍然需要满足有偶数个2配对形成“1 4 1 4 1 4 1 2 2 2 2”。如果是奇数个2,就要减少1的个数,让2插空到4之间,形成“1 4 1 4 2 4 2 2 2 2”
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int n = Integer.parseInt(br.readLine());
            String[] strs = br.readLine().split(" ");
            int canDivBy4 = 0, canDivBy2 = 0, canDivBy1 = 0;
            for(String strNum: strs){
                int num = Integer.parseInt(strNum);
                if(num % 4 == 0){
                    canDivBy4++;
                }else if(num % 2 == 0){
                    canDivBy2++;
                }else{
                    canDivBy1++;
                }
            }
            if(canDivBy1 + (canDivBy2 % 2) <= canDivBy4 + 1){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }
}

编辑于 2022-02-26 22:06:12 回复(0)