首页 > 试题广场 >

重排数列

[编程题]重排数列

热度指数：285 时间限制：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

算法知识视频讲解

昵称已被占用、

总结归纳：遍历序列，统计能被4整除的数和只能被2整除的数。
n4 >= n / 2或者(double)n2 >= (n - n2) / 2

public class Sort {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        try {
            in = new Scanner(new FileInputStream("F:\\java\\JavaLearning\\src\\nowcoder\\pastexampapers\\Sort"));
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        int testNum = in.nextInt();
        for (int i = 0; i < testNum; i++) {
            int n = in.nextInt();
            int[] seq = new int[n];
            for (int j = 0; j < n; j++) {
                seq[j] = in.nextInt();
            }
            process(seq);
        }
    }
    private static void process(int[] seq) {

        int fourTimeCount = 0;
        int twoTimeCount = 0;
        for (int i : seq) {
            if ((i & 3) == 0) {
                fourTimeCount++;
            } else if ((i & 1) == 0) {
                twoTimeCount++;
            }
        }

        if (fourTimeCount >= seq.length / 2) {
            System.out.println("Yes");
        } else if (fourTimeCount >= (seq.length - twoTimeCount) / (double)2) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

编辑于 2018-07-25 21:49:28 回复(0)

Java

热爱code的涛涛

本人还是个菜鸟，是这么理解的：
4的倍数>=奇数-1 插空法排序

import java.util.Scanner;
public class 重排数列 {
    public static void solution() {
        Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        String[] res=new String[2^31];
        int index=0;
        for(int i=0;i<t;i++) {
            int n=in.nextInt();
            int four=0;
            int two=0;
            int[] A=new int[n];
            for(int j=0;j<n;j++) {
                A[j]=in.nextInt();
                if(A[j]%4==0) {
                    four++;
                }else if(A[j]%2==0) {
                    two++;
                }
                if(j==n-1) {
                    if(four>=n-four-1) {
                        res[index++]="Yes";
                    }else if(four>=n-two-four){
                        res[index++]="Yes";
                    }else {
                        res[index++]="No";
                    }
                }
            }
        }
        for(String a:res) {
            if(a!=null) {
                System.out.println(a);
            }
        }
    }

    public static void main(String[] args) {
        solution();
    }
}

发表于 2019-09-20 17:05:58 回复(1)

2033329616

只要满足被4整除的个数比无法被2整除的数多或相等就可以满足题意。

 def result():
    t = int(input().strip())
    for i in range(t):
        n = int(input().strip())
        num_list = list(map(int, input().strip().split(' ')))
        times_no = 0
        times_4 = 0
        for data in num_list:
            if data % 4 == 0:
                times_4 += 1
            elif data % 2 != 0:
                times_no += 1
        if times_4 >= times_no:
            print('Yes')
        else:
            print('No')
result()

发表于 2019-08-26 20:16:46 回复(0)

Disconnect

n = input()
n = int(n)
for i in range(n):
    m  = input()
    m = int(m)
    mlst = list(map(int,input().split()))
    con4,con2 = 0,0
    for i in mlst:
        if i%4==0:
            con4+=1
        elif i%2==0:
            con2+=1
    if con2<2:
        con2=0
    if m%2!=0:
        m = m-1
    if con2+con4*2>=m:
        print("Yes")
    else:
        print("No")

发表于 2018-12-27 22:37:28 回复(0)

Marbin

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();

    while(t > 0){
        int n = in.nextInt();
        int[] A = new int[n + 1];
        int f = 0;
        int k = 0;
        for(int i = 1; i < n + 1; i++){
            A[i] = in.nextInt();
            if(A[i] % 4 == 0)
                f++;
            else if(A[i] % 4 == 1 || A[i] % 4 == 3)
                k++;
        }
        if(f >= (n / 2) || k <= f)
            System.out.println("Yes");
        else
            System.out.println("No");

        t--;
    }

}

}

发表于 2018-08-29 17:10:01 回复(0)

你们之后会让hr联系我的

def func(data_list):
    for i in data_list:
        count4 = 0
        count2 = 0
        count1 = 0
        for j in i:
            if j % 4 == 0:
                count4 += 1
            elif j % 2 == 0:
                count2 += 1
            else:
                count1 += 1
        if count2 == 0:
            if count4 - count1 >= -1:
                print 'Yes'
            else:
                print 'No'
        else:
            if count4 - count1 >= 0:
                print 'Yes'
            else:
                print 'No'


if __name__ == '__main__':
    data_list = []

    t = input()
    for i in range(t):
        n = input()
        data = raw_input().strip().split(' ')
        data = map(int, data)
        data_list.append(data)

    func(data_list)

编辑于 2018-08-17 17:30:35 回复(0)

菜菜真的菜

#include<iostream>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int cnt1=0;
        int cnt2=0;
        int cnt4=0;
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            if(temp%4==0)
                cnt4++;
            else if(temp%2==0)
                cnt2++;
            else
                cnt1++;
        }
        if(cnt2%2==0)
        {
            if(cnt4>=cnt1-1)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        else
        {
            if(cnt4>=cnt1)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

发表于 2018-07-28 15:59:47 回复(0)