重排数列
2018-05-06 本文已影响0人
vckah
题目:对数列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 or No
思路: - 任意数和 4 的倍数相乘,那么肯定能被 4 整除
- 如果存在多个 2 的倍数,彼此两两相乘也能被 2 整除
- 统计能被 4 整除的个数,能被 2 整除的数(不包括能被 4 整除的数),其他数个数
- 判断能被 4 整除的个数要 >= 其他数个数
C++ 的输入几组数还是非常赞的
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
int n;
int a[10000];
while(t)
{
int mod2 = 0;
int mod4 = 0;
cin>>n;
for(int i = 0; i<n; i++)
{
cin>>a[i];
}
for(int i=0; i<n; i++)
{
if(a[i] % 4 == 0)
mod4++;
else if(a[i] % 2 == 0)
mod2++;
}
if(mod4 >= ( n - mod2 - mod4))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
t--;
}
}