[02]重排数列-网易2018秋

1.题目描述

小易有一个长度为 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
  

• 输出例子 1:

  Yes
  No
  

2.题目解析

从最简单情况分析

数列数字个数	可能情况
1	4的倍数/奇数/不能被4整除的偶数
2	4的倍数×奇数/不能被4整除的偶数×不能被4整除的偶数
3	奇数×4的倍数×奇数/不能被4整除的偶数×不能被4整除的偶数×不能被4整除的偶数/奇数×4的倍数×不能被4整除的偶数
4	奇数×4的倍数×奇数×4的倍数/不能被4整除的偶数×不能被4整除的偶数×不能被4整除的偶数×不能被4整除的偶数/奇数×4的倍数×不能被4整除的偶数×不能被4整除的偶数

分析各种情况

• 奇数与4的倍数关系
  奇数×4的倍数×奇数×4的倍数×奇数
  奇数×4的倍数×奇数×4的倍数
  4的倍数数目 >= 奇数数目-1

• 奇数与偶数关系
  奇数×4的倍数×奇数×4的倍数×不能被4整除的偶数×不能被4整除的偶数×不能被4整除的偶数
  4的倍数数目 >= 奇数数目

关键在于分析：什么情况下数列满足要求？
奇数和能被4整除的数交叉排列才能满足要求，但是要重点分析以下两种情况：

结论

1. 没有不能被4整除的偶数，4的倍数数目 >= 奇数数目-1
2. 有不能被4整除的偶数，4的倍数数目 >= 奇数数目

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t = 0; // 数列的个数
    scanf("%d",&t);
    for(int j=0;j<t;++j){
        int n = 0;
        scanf("%d",&n);
        int nums[n];// 定义存放n个数据的数组
        for(int i=0;i<n;++i){
            scanf("%d",&nums[i]);
        }
        int count4 = 0; // 四的倍数个数
        int count2 = 0; // 被2整除不被4整除的个数 
        int odd = 0; // 奇数
        for(int i=0;i<n;++i){
            if(nums[i]%2==1){
                ++odd;
            }else if(nums[i]%4==0){
                ++count4;
            }else{
                ++count2;
            }
        }
        if(count2 == 0){
            if(count4>=odd-1){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }else{
            if(count4>=odd){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}

#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;
}

牛课题目