首页 > 试题广场 >

重排数列

[编程题]重排数列

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

算法知识视频讲解

C/C++

幼师的攻城狮

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t; // 数列个数
  scanf("%d", &t); 
  for(int k=0;k<t;++k) {
    int n;
    scanf("%d", &n); // 数列长度 
    int cnt4 = 0; // 四倍数计数
    int cnt2 = 0; // 偶数计数
    int cnt1 = 0; // 奇数计数
    for (int i = 0; i < n; i++) { // 获取数列数据
      int x;
      scanf("%d", &x);
      // 更新统计
      if (x % 4 == 0)
        cnt4++;
      else if (x % 2 == 0)
        cnt2++;
      else
        cnt1++;
    }
    // 统计判断
    if (cnt2 == 0) { // 情况1
      if (cnt4 >= cnt1 - 1)
        printf("Yes\n");
      else
        printf("No\n");
    } else { // 情况2
      if (cnt4 >= cnt1)
        printf("Yes\n");
      else
        printf("No\n");
    }
  }
  return 0;
}

发表于 2018-11-04 11:49:11 回复(0)

Disconnect

t = input()
t = int(t)
for k in range(t):
    n = input()
    n = int(n)
    con4,con2 = 0,0
    lst = list(map(int,input().split()))
    for i in range(n):
        if lst[i]%4==0:
            con4+=1
        elif lst[i]%2==0:
            con2+=1
    if con2==1:
        con2=0
    if n%2==0:
        if con4*2+con2>=n:
            print("Yes")
        else:
            print("No")
    else:
        if con4*2+con2>=n-1:
            print("Yes")
        else:
            print("No")

发表于 2018-12-24 00:11:50 回复(0)