stebest
V2EX  ›  iCode

问一道 code 题

By stebest at 2017 年 11 月 11 日 · 10554 次点击

之前刷题的时候遇到一个题目,感觉做法没错,但是总是不通过,可能是当局者迷,不知道有没有人能帮忙找出来。

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

这样就是可以通过的。
弄不清楚错在哪了。

11 条回复    2017-11-11 19:02:12 +08:00
neosfung
   1
neosfung  
   2017 年 11 月 11 日
if((n4>=n1) ||((n4>= n1-1) &&(n4+n1 == n)))
这句再想想
stebest
   2
stebest  
OP
   2017 年 11 月 11 日
@neosfung 大致想法是如果 4 的倍数的数目大于等于奇数的数目,那么肯定是可以的。后面那个大于等于和等于一样,如果 4 的倍数的数目比奇数数目少一,这种情况只有不存在只是 2 的倍数 n2 时候才能够满足,由于 n1+n2+n4==n,所以这样写的
neosfung
   3
neosfung  
   2017 年 11 月 11 日
@stebest 的确,仔细思考,你的方法是没问题的。会不会输入读取弄错了啊
stebest
   4
stebest  
OP
   2017 年 11 月 11 日
@neosfung 没有,我测试了一下,里面那个注释的语句,输出的数目都是对的,但还是搞不清楚错在哪。
iEverX
   5
iEverX  
   2017 年 11 月 11 日
printf \n
iEverX
   6
iEverX  
   2017 年 11 月 11 日
以及,有 t <= 10 的条件?
neosfung
   7
neosfung  
   2017 年 11 月 11 日
是输入读取弄错了,我改成你给的第二种方法的输入读取,就过了
neosfung
   8
neosfung  
   2017 年 11 月 11 日   ❤️ 1
具体是
scanf("%d",&n);
这一行,你要放到循环里面。。。
stebest
   9
stebest  
OP
   2017 年 11 月 11 日 via Android
@neosfung 这个我倒没注意,一会试试
stebest
   10
stebest  
OP
   2017 年 11 月 11 日 via Android
@iEverX 这个是里面题目给的,没有问题的,我没说因为重点不在这。
stebest
   11
stebest  
OP
   2017 年 11 月 11 日 via Android
@neosfung 好像是这个问题,,,我以为 n 都是一样的,还是审题不仔细。。😂
© 2026 V2EX · 23ms · 3.9.8.5