首页 > 试题广场 >

重排数列

[编程题]重排数列
  • 热度指数：219 时间限制：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
算法知识视频讲解
添加回答
努力学习天天向上_0头像 努力学习天天向上_0
<p>c4为4的倍数 c2为2的倍数 c1为基数</p><p>c4个数大于等于数列的一半 或 c4个数大于等于c1个数 或 全都为c2</p><p><br></p>
发表于 2020-08-08 14:44:38 回复(0)
牛客337377036号头像 牛客337377036号
4的倍数的数大于等于奇数的数就一定可以，然后就很简单了
唯一的问题是，凭啥Java做的找不到mian类啊，离谱 
#include<iostream>
using namespace std;
 
string ys(int arr[],int n){
        int arr1[100000];
        int j = 0,c = 0;
        for (int i = 0; i < n; i++) {
            if(arr[i]%4!=0){
                arr1[j] = arr[i];
                j++;
            }
        }
        for (int i = 0; i < j; i++) {
            if(arr1[i]%2!=0) c++;
        }
        if(n-j>=c) return "Yes";
        else return "No";
    }
int main(){
    int arr[100000];
    int m = 0;
    int n;
    cin>>n;
    while(n!=0) {
        cin>>m;
        for (int i = 0; i < m; i++) {
            cin>>arr[i];
        }
        n--;
        cout<<ys(arr, m)<<endl;
    }
}


发表于 2022-08-11 15:30:08 回复(0)
kilowatt头像 kilowatt
你好，为什么我的输入和测试用例一样， 
#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
    int turns;
    while(cin>>turns)
    {
        vector<vector<int>> table;
        for (int i=0;i<turns;i++)
        {
            int length;
            cin>>length;
            table.push_back({});
            table[i].resize(length);
            for (int k=0;k<length;k++)
            {
                int num;
                cin>>num;
                table[i][k]=num;
            }
        }
        for (int i=0;i<turns;i++)
        {
            int length=(int)table[i].size();
            int have=0;
            int have2=0;
            for (int k=0;k<length;k++)
            {
                if (table[i][k]%4==0)
                {
                    have+=1;
                }
                else if (table[i][k]%2==0)
                {
                    have2+=1;
                }
            }
            //have最多能解决havex2+1个数，剩下的靠have2内部解决
            if (have2>=length-have*2-1)
            {
                cout<<"Yes"<<" ";
            }
            else
            {
                cout<<"No"<<" ";
            }
        }
        cout<<endl;
    }
}

但是却提示我通过0个用例？
发表于 2020-08-13 20:14:05 回复(0)
提交观点

问题信息

贪心 动态规划 数组 网易 测试开发工程师 2018 数学
上传者：小小
难度：
3条回答 2721浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号