之前刷题的时候遇到一个题目,感觉做法没错,但是总是不通过,可能是当局者迷,不知道有没有人能帮忙找出来。
小易有一个长度为 N 的正整数数列 A = {A[1], A[2], A[3]..., A[N]}。
牛博士给小易出了一个难题:
对数列 A 进行重新排列,使数列 A 满足所有的 A[i] * A[i + 1](1 ≤ i ≤ N - 1)都是 4 的倍数。
小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。
主要方法是寻找能被 4 整除和只能被 2 整除的数, 代码如下:
#include <stdio.h>
int Isarray(int n, int a[100000])
{
int n1=0,n2=0,n4=0,i;
for(i=0;i<n;i++)
{
if(a[i]%4==0)
++n4;
else if(a[i]%2==0)
++n2;
else
++n1;
}
//printf("%d,%d,%d,%d\t",n1,n2,n4,n);
if (n==1 && n4 )
return 1;
if((n4>=n1) ||((n4>= n1-1) &&(n4+n1 == n)))
return 1;
else
return 0;
}
int main(void)
{
int i,j,t,n,a[100000],b[10];
scanf("%d",&t);
scanf("%d",&n);
for(j=0;j<t;j++)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
b[j]=Isarray(n,a);
}
for(j=0;j<t;j++)
if(b[j])
printf("Yes");
else
printf("No");
return 0;
}
但是我看类似的代码,比如:
#include <stdio.h>
int n;
int arr[100100];
int countMod4, countMod2;
void read() {
countMod4 = 0;
countMod2 = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
if (arr[i] % 4 == 0) {
++countMod4;
} else if (arr[i] % 2 == 0) {
++countMod2;
}
}
}
void work() {
int countOdd = n - countMod4 - countMod2;
if ((n == 1 && countMod4) || countMod4 >= countOdd - !countMod2) {
puts("Yes");
} else {
puts("No");
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
read();
work();
}
return 0;
}
这样就是可以通过的。
弄不清楚错在哪了。
1
neosfung 2017-11-11 16:27:14 +08:00
if((n4>=n1) ||((n4>= n1-1) &&(n4+n1 == n)))
这句再想想 |
2
stebest OP @neosfung 大致想法是如果 4 的倍数的数目大于等于奇数的数目,那么肯定是可以的。后面那个大于等于和等于一样,如果 4 的倍数的数目比奇数数目少一,这种情况只有不存在只是 2 的倍数 n2 时候才能够满足,由于 n1+n2+n4==n,所以这样写的
|
5
iEverX 2017-11-11 17:05:36 +08:00
printf \n
|
6
iEverX 2017-11-11 17:09:20 +08:00
以及,有 t <= 10 的条件?
|
7
neosfung 2017-11-11 17:10:06 +08:00
是输入读取弄错了,我改成你给的第二种方法的输入读取,就过了
|
8
neosfung 2017-11-11 17:18:32 +08:00 1
具体是
scanf("%d",&n); 这一行,你要放到循环里面。。。 |