问一道 code 题

2017-11-11 16:14:38 +08:00
 stebest

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

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

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

8717 次点击
所在节点   iCode
11 条回复
neosfung
2017-11-11 16:27:14 +08:00
if((n4>=n1) ||((n4>= n1-1) &&(n4+n1 == n)))
这句再想想
stebest
2017-11-11 16:30:37 +08:00
@neosfung 大致想法是如果 4 的倍数的数目大于等于奇数的数目,那么肯定是可以的。后面那个大于等于和等于一样,如果 4 的倍数的数目比奇数数目少一,这种情况只有不存在只是 2 的倍数 n2 时候才能够满足,由于 n1+n2+n4==n,所以这样写的
neosfung
2017-11-11 16:41:26 +08:00
@stebest 的确,仔细思考,你的方法是没问题的。会不会输入读取弄错了啊
stebest
2017-11-11 16:46:54 +08:00
@neosfung 没有,我测试了一下,里面那个注释的语句,输出的数目都是对的,但还是搞不清楚错在哪。
iEverX
2017-11-11 17:05:36 +08:00
printf \n
iEverX
2017-11-11 17:09:20 +08:00
以及,有 t <= 10 的条件?
neosfung
2017-11-11 17:10:06 +08:00
是输入读取弄错了,我改成你给的第二种方法的输入读取,就过了
neosfung
2017-11-11 17:18:32 +08:00
具体是
scanf("%d",&n);
这一行,你要放到循环里面。。。
stebest
2017-11-11 17:27:42 +08:00
@neosfung 这个我倒没注意,一会试试
stebest
2017-11-11 17:28:18 +08:00
@iEverX 这个是里面题目给的,没有问题的,我没说因为重点不在这。
stebest
2017-11-11 19:02:12 +08:00
@neosfung 好像是这个问题,,,我以为 n 都是一样的,还是审题不仔细。。😂

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/405553

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX