首页 > 试题广场 >

重排数列

[编程题]重排数列
  • 热度指数:11000 时间限制: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和不可以被2整除的数的个数
//一个不可以被4和2整除的数周围必须有2个可以被4整除的数,除了第一个
//那么对于每一个n1都必须有一个属于它的n4,如果没有n2,那第一个n1可以和第2个共有一个
//所以就是 n4>=n1||(n2==0&&n4>=n1-1)
#include<iostream> using namespace std; int main(){     int n;     int l;     int num;     int n1,n4;     while(cin>>n){         for(int i = 0;i<n;i++){             cin>>l;             n1 = 0;             n4 = 0;             for(int j = 0;j<l;j++){                 cin>>num;                 if(num%4==0)                     n4++;                 else if(num%2!=0)                     n1++;             }             if(n4>=n1||(n4>=n1-1&&(n4+n1)==l))                 cout<<"Yes"<<endl;             else                 cout<<"No"<<endl;                       }     }     return 0; }

编辑于 2017-09-10 22:00:24 回复(7)
分类讨论下。
  • 显然,任意数和 4 的倍数相乘,其结果仍是 4 的倍数;
  • 显然,若存在任意数量 2 的倍数,两两之间乘起来就是 4 的倍数;
  • 如果存在一个数不是 2 的倍数,即它是一个奇数:
    • 放在 2 的倍数旁边,一定不符合要求;
    • 放在 4 的倍数旁边,相乘结果仍是 4 的倍数。

因此符合要求的排列分两种情况:
  1. 存在 2 的倍数,所有 2 的倍数相邻排列,需要一个 4 的倍数连接剩下的数,奇数最多和 4 的倍数数量相等,要求 mod4_num >= odd
  2. 没有 2 的倍数,原本放 2 的倍数一端可以改放一个奇数,mod4_num >= odd - 1
import java.util.Scanner;
public class Main {    
    public static void  main(String[] args){
        Scanner in = new Scanner(System.in);
        //ArrayList<String> list = new ArrayList<String>();
        while(in.hasNext()){
            int t = in.nextInt();
            for(int i = 0;i<t;i++){
                int n = in.nextInt();
                int a[] = new int[n];
                for(int j = 0;j<n;j++){
                    a[j] = in.nextInt();
                }    
                int mod4_num=0 , mod2_num=0,odd=0;
                for(int k = 0;k<a.length;k++){
                    if(a[k] % 4 ==0){
                        mod4_num++;
                    }else if(a[k] % 2 ==0){
                        mod2_num++;
                    }else{
                        odd++;
                    }
                }
                if(mod2_num > 0){
                    if(mod4_num >= odd){
                        System.out.println("Yes");
                    }else{
                        System.out.println("No");
                    }
                }else{
                    if(mod4_num >=(odd-1)){
                        System.out.println("Yes");
                    }else{
                        System.out.println("No");
                    }
                }
            }
        }
 
    }
}

编辑于 2017-10-08 00:33:01 回复(5)

///  这个是根据AC的同学讲解的思路,很好理解
/**

数组两种情况: 1. 由4的倍数和奇数组成,只需要满足 numOfFour >= odds-1;
                       2. 存在4的倍数,只能被2整除的数和奇数,只需要将只能被2整除的数放在一起即可
                           数组中需要 numOfFour >= odds 即可,如6,14,18,4,奇数,4,奇数......
**/


   
编辑于 2017-09-09 19:29:58 回复(0)
#include<stdio.h>
int main(){
    int T,n,i,x;
    for(scanf("%d",&T);T--;){
        int cnt1=0,cnt2=0,cnt4=0;
        for(scanf("%d",&n),i=0;i<n;i++){
            scanf("%d",&x);
            if(x%4==0) cnt4++;
            if(x%2==0&&x%4!=0) cnt2++;
            if(x%2==1) cnt1++;
        }
        printf("%s\n",cnt2==0?(cnt4>=cnt1-1?"Yes":"No"):(cnt4>=cnt1?"Yes":"No"));
    }
}

发表于 2017-09-18 19:50:38 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        List<int[]> list = new ArrayList<>();
        String[] result = new String[t];
        for(int i = 0;i<t;i++){
            int num = sc.nextInt();
            int[] tt = new int[num];
            for(int j = 0;j<num;j++){
                tt[j] = sc.nextInt();
            }
            list.add(tt);
        }
        for(int i = 0;i<list.size();i++){
            int[] flag = new int[list.get(i).length];
            for(int j =0;j<list.get(i).length;j++){
                if(list.get(i)[j]%2==0){
                    flag[j] = 1;
                }
                if(list.get(i)[j]%4==0){
                    flag[j] = 2;
                }
            }
            int ff=0;
            for(int k = 0;k<flag.length;k++){
                ff += flag[k];
            }
            if(ff>=flag.length){
                result[i] = "Yes";
            }
            else {
                result[i] = "No";
            }
        }
        for (String rr:result
             ) {
            System.out.println(rr);
        }

    }
}
思路就是2的倍数为1,4的倍数为2,所有值加起来要大于等于长度
发表于 2022-02-12 21:39:18 回复(0)
#include<iostream>
#
include<vector>
#include<string>
#
include <sstream>
#include <math.h>
#
include<algorithm>
#include<limits.h>
#
include<unordered_map>
#include<unordered_set>
using namespace std;
bool solve(vector<int> & v){
    vector<int> count(3,0);
    for(int n:v){
        if(n%2==1){
            count[0]++;
        }else if(n%4!=0){
            count[1]++;
        }else{
            count[2]++;
        }
    }
    if(count[1]==0 )
        return count[2]>=count[0]-1;
    return count[2]>=count[0];
}
int main(){
 int num;
    cin>>num;
 for(int i=0;i<num;i++){
        int n;
        cin>>n;
        vector<int> v(n);
        for(int j=0;j<n;j++){
            cin>>v[j];
        }
        cout<<(solve(v)?"Yes":"No")<<endl;
 }
}
发表于 2020-03-02 21:25:42 回复(0)
参考了前面高赞的回答的思路,稍作改进:
把count2>1与否分为两种情况的处理,若count2=1或count2=0时,可以把2的倍数视为只是一个普通的不能被4整除的数
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            for (int i = 0; i < n; i++) {
                int length = in.nextInt();
                int count4 = 0;
                int count2 = 0;
                for (int j = 0; j < length; j++) {
                    int num = in.nextInt();
                    if (num % 4 == 0) {
                        count4++;
                    } else if (num % 2 == 0) {
                        count2++;
                    }
                }
                if (count2 > 1) {
                    if (count4 >= length - count2 - count4 - 1) {
                        System.out.println("Yes");
                    } else {
                        System.out.println("No");
                    }
                } else {
                    if (count4 >= length - count4 - 1) {
                        System.out.println("Yes");
                    } else {
                        System.out.println("NO");
                    }
                }
            }
        }
    }
}


发表于 2019-08-11 10:55:09 回复(0)
public class Main4 {
    public static void main(String[] args) {
        //预处理数据 可以不保存到内存,我这图个省事。
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[][] arrs = new int[count][];
        for (int i = 0; i < arrs.length; i++){
            int arrLength = sc.nextInt();
            arrs[i] = new int[arrLength];
            for(int j = 0; j < arrLength; j++){
                arrs[i][j] = sc.nextInt();
            }
        }
        sc.close();
        for (int[] arr : arrs){
            int counter = 0;
            for(int i = 0; i < arr.length; i++){
                counter += (((arr[i] & 1) == 1) ? 1 : ((arr[i] & 3) == 0) ? -1 : 0);//是否为奇数如果为奇数+1, 如果能被4整除 -1 , 否则 +0
            }
            System.out.println(counter <= 0 ? "Yes" : "No");//如果为4的倍数的数大于或等于包含奇数的数量
        }
    }
}


发表于 2019-07-03 12:00:16 回复(0)
(以下以4代表能被4整除的数,2代表偶数(不包括能被4整除的数),1代表奇数)
奇数肯定要放在4旁边,2两两放在一起,所以以下形式就是最优解:
1-4-1-4-(~~~)-4-2-2-2-(~~~)
按照这种形式的话,4要大于等于1的个数,2随意。
编程思路就是找出1和4的个数,然后判断一下。
发表于 2018-05-07 11:50:37 回复(0)
首先考虑一下极端情况:
1.不论数组有多大。每个元素都为2(即都是2的倍数),这时2的个数等于数组大小,
显然是符合公式的;
2.只有两个奇数和一个4(即只有一个4的倍数,按照141的顺序排列),这时候每增加
一个4都可以再增加一个任意元素,这时候4的个数乘2加1等于数组大小;
综合这两种情况:
只需要遍历数组知道是4和2的倍数的元素到底有多少就可以确定输出结果了,
代码如下:
import java.util.ArrayList;
import java.util.Scanner;
public class Test06 {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int k = sc.nextInt();
        ArrayList<ArrayList<Integer>> aLists = new ArrayList<>();
        while(k>0) {
            int n = sc.nextInt();
            ArrayList<Integer> aList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                aList.add(sc.nextInt());
            }
            aLists.add(aList);
            k--;
        }
        sc.close();
        for (int i = 0; i < aLists.size(); i++) {
            int n2 = 0;//统计2的倍数
            int n4 = 0;//统计4的倍数
            ArrayList<Integer> aList = aLists.get(i);
            for (int j = 0; j < aList.size(); j++) {
                if (aList.get(j)%4==0) {
                    n4++;
                }else if (aList.get(j)%2==0) {
                    n2++;
                }
            }
            if ((n4*2+n2+1)>=aList.size()) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
}

编辑于 2018-03-28 17:05:29 回复(0)
思路:如果一个数是4的倍数,那么他可以附带照顾另一个数;
如果一个数仅是2的倍数,那么他只能照顾自己,他周围的数也必须是2或4的倍数;
所以:
统计是4倍数的数的个数a,统计不是4,但是2的倍数的数b,只要2*a+b>=数列个数就好了。


importjava.util.*;
publicclassMain {
publicstaticvoidmain(String[] args) {
Scanner in = newScanner(System.in);
intcount = Integer.parseInt(in.nextLine());
ArrayList<Boolean> result = newArrayList<>();
for(inti = 1;i<=count;i++){
intnum = Integer.parseInt(in.nextLine());
intbase2 = 0;
intbase4 = 0;
String[] indata = in.nextLine().split(" ");
for(String e:indata){
intval = Integer.parseInt(e);
if(val%4==0)
base4++;
else{
if(val%2==0)
base2++;
}
}
if(base2+base4*2>=num)
result.add(true);
else
result.add(false);
}
for(booleane:result){
if(e)
System.out.println("Yes");
else
System.out.println("No");
}
}
}

编辑于 2018-03-25 21:06:39 回复(0)
奇数的个数小于等于(是4的倍数的数的个数),则返回Yes,否则返回No
private static String getResult(int[] input){
        int countOdd = 0,countFour = 0;
        for(int i = 0;i < input.length; i++){
            if(input[i]%2 == 1){countOrd++;}
            if(input[i]%4 == 0){countFour++;}
        }
        if(countOrd <= countFour){return "Yes";}else{return "No";}
    }

发表于 2018-03-20 22:12:16 回复(1)

var n=readline();
for(;n>0;n--){
    var m4=0;
    var m1=0;
    var i=readline();
    var arr=readline().split(' ');
    for(var j=0;j<i;j++){
        if(arr[j]%4==0){m4++;}
        if(arr[j]%2==1){m1++;}
    }
    if(m1-m4>1) {
        print("No");
    }
    else{
        print("Yes");
    }
}
发表于 2017-12-20 20:57:38 回复(0)
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            int n1=0;
            int n4=0;
            for(int j=0;j<n;j++){
                int num=sc.nextInt();
                if(num%4==0) n4++;//统计4的倍数的个数
                else if(num%2==1) n1++;//统计奇数的个数
            }
            //只有n1+n4的个数小于n,且n1大于n4时,输出No,其他情况都是Yes
            if(n1+n4<n&&n1>n4) System.out.println("No");
            else System.out.println("Yes");
        }
    }
}

编辑于 2017-10-14 22:54:57 回复(0)

语言:C++ 运行时间: 308 ms 占用内存:376K 状态:答案正确
每个数都按规则变成0,1,2,能被4整数变为2,被2整除变为1,否则为0。
问题转化为相邻两数之和大于等于2。所以所有相邻两数和的和至少为2*(n-1)。
因为所有相邻两数和的和把端点计算了1次,其余点计算了2次。据此判断一下即可。
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)上,持续更新。

#include <iostream>
using namespace std;
int main()
{
    int t; cin >> t;
    for (int i = 0; i < t; i++) {
        int n; cin >> n;
        int sum = 0, num;
        bool iftwo = false;
        for (int j = 0; j < n; j++) {
            cin >> num;
            if (num % 4 == 0) {
                sum += 2;
                iftwo = true;
            }
            else if (num % 2 == 0) sum += 1;
        }
        if (sum > n - 1) cout << "Yes" << endl;
        else if (sum == n && iftwo) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
发表于 2017-10-10 10:35:30 回复(1)
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int t=0,n=0;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int temp=0,k4=0,k2=0,k1=0;
        for(int i=0; i<n; i++)
        {
            cin>>temp;
            if(temp%2==0)
            {
                if(temp%4==0)
                    k4++;
                else if((k2+k4)<2)
                    k2++;
            }
            else
                k1++;
        }
        if(k1>k4)
            cout<<"No"<<endl;
        else if((k2+k4)<2)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
}


题目在数列中数的个数即 n=1 时说明好像并不清晰,如测试组中有 1  494 对于这组数列494并不整除4,但系统判定输出Yes,不是很明白其原因

编辑于 2017-09-29 20:45:02 回复(0)
import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int[] array;
    static int length;
    static int fourCount;
    static int twoCount;
    static StringBuilder sb=new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner scanner=new Scanner(System.in);
        int i,j=0;
        int times=scanner.nextInt();
        for(;j<times;j++){
            fourCount=twoCount=0;
            length=scanner.nextInt();
            array=new int[length];
            for(i=0;i<length;i++){
                array[i]=scanner.nextInt();
            }
            exe();
        }
//必须要符合规范 提交了好几次真伤心
        sb=sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }
    public static void exe(){
        for(int i:array){
            if(isFour(i)){
                fourCount+=1;
            }else if(isTwo(i)){
                twoCount+=1;
            }
        }
        if(fourCount>=(length-twoCount+1)>>1){
            sb.append("Yes\n");
        }else{
            sb.append("No\n");
        }
    }
    //判断是否为4的倍数
    public static boolean isFour(int n) {
        return 0 == (n & 3) ? true : false;
    }
    //判断是否为2的倍数
    public static boolean isTwo(int n){
        return 0 == (n & 1) ? true :false;
    }
}
发表于 2017-09-28 21:04:38 回复(0)
/*数列中的数分为3类 :1、奇数  2、能被4整除的偶数 3、能被2整除但是不能被4整除的偶数   这三类数代号分别为  A B C
当C=0的时候,我们只要满足B>C就行了,数列类似于这样:A B A B A,这样肯定满足要求,当然B越多就更满足要求了
当C>0的时候,我们只要满足B>=C就行了,数列类似于这样 C B A B A,,这样肯定满足要求,当然C越多,没关系,多个C之间两两组合也满足要求*/

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int>vec;
    int t;
    cin>>t;
    for(int j=0;j<t;j++)
    {
        int n,number,cnt4=0,cnt2=0,cntodd=0;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>number;
            if(number%4==0) cnt4++;
            else if(number%2==0) cnt2++;
            else cntodd++;
        }
        if(cnt2==0&&cntodd-cnt4<=1) vec.push_back(1);
        else if(cnt2>0&&cntodd-cnt4<=0) vec.push_back(1);
        else vec.push_back(0);
    }
    for(int j=0;j<t;j++)
    {
        if(vec[j]==0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
发表于 2017-09-16 09:49:53 回复(0)
按照楼上大神“云y”的思路,果然通过了,可是作为小白的我还是不太明白这具体是什么意思,求大神解析
a = input()
for i in range(a):
    total = 0
    num = 0
    x_1 = input()
    x = raw_input().split()
    for m in x:
        if int(m) % 4 == 0:
            total += 1
        elif int(m) % 2 == 0:
            num += 1
    if num == 0:
        if len(x)-total <= total+1:
            print 'Yes'
        else:
            print 'No'
    else:
        if len(x)-total-num+1 <= total+1:
            print 'Yes'
        else:
            print 'No'
发表于 2017-09-09 21:41:06 回复(2)
可以把输入的数字分成三类,1.能被2整除却不能被4整除、2.能被4整除、3.不能被2整除。
其中只是要求可以满足该种排列的,可以假设所有1类的数放在最前面,此时满足条件;然后后面必然接一个2类数,后面接3类数或2类数。
因此只需要满足2类数不少于3类数这个条件即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
usingnamespacestd;
 
intmain()
{
    intn;
    cin>>n;
    for(inti = 0; i < n; i++)
    {
        intnum;
        cin>>num;
        inta;
        intisf[3] = {0};
        for(intj = 0; j < num; j++)
        {
            cin>>a;
            if(a % 2 == 0 && a % 4 != 0)
                isf[1]++;
            elseif(a % 4 == 0)
                isf[2]++;
            else
                isf[0]++;
        }
        if(isf[2] < isf[0])
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
}

发表于 2018-03-26 21:53:40 回复(0)