之前刷题的时候遇到一个题目,感觉做法没错,但是总是不通过,可能是当局者迷,不知道有没有人能帮忙找出来。
小易有一个长度为 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 |
![]() | nbsp; 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 ![]() 具体是 scanf("%d",&n); 这一行,你要放到循环里面。。。 |