[已解决]求解关于数组相邻数字之间奇偶排列问题

灯火阑珊201

Calabash面临一个难题，快来帮帮他。给定一个个数为n的数组，a1,a2,…,an ，当数组中两项ai，aj满足
|i−j|=1，可以交换这两项。那么最少需要交换多少次，可以使任意相邻的两项奇偶性不同？
输入
包含多组测试样例。
第一行，为样例数t(1≤t≤104)。
每组测试样例第一行，为数组中项的个数n，接下来一行是数组a1,a2,…,an(1≤ai≤109)。

所有t组输入数据的a数组长度之和不超过105。
输出
对每组样例输出最少的交换次数，如果任意次数的交换都不能满足条件输出-1。
样例输入 Copy
5
3
6 6 1
1
9
6
1 1 1 2 2 2
2
8 6
6
6 2 3 4 5 1
样例输出 Copy
1
0
3
-1
2


我的代码如下，不知道哪里有问题
#include<stdio.h>
int main()
{
        int m,n,t,f[100000],i,x,w,a,b,jishu;
        scanf("%d",&m);
        for(t=0; t<m; t++)
        {
                x=0;
                scanf("%d",&n);
                for(i=0; i<n; i++)
                {
                        scanf("%d",&f[i]);
                        if(f[i]%2==0)
                        {
                                f[i]=0;
                                x++;
                        }
                        else
                        {
                                f[i]=1;
                                jishu++;
                        }
                }
                if(x<(n/2)||x>((n+1)/2))
                {
                        printf("-1\n");
                        continue;
                }
                if(n%2==0)
                {
                        for(i=0,w=1,a=0; i<n; i++)
                        {
                                if(f[i]==1)
                                {
                                        if(i+1>w)a+=i+1-w;
                                        else a+=w-i-1;
                                        w=w+2;
                                }
                        }
                        for(i=0,w=2,b=0; i<n; i++)
                        {
                                if(f[i]==1)
                                {
                                        if(i+1>w)b+=i+1-w;
                                        else b+=w-i-1;
                                        w=w+2;
                                }
                        }
                        if(a>b)printf("%d\n",b);
                        else printf("%d\n",a);
                }
                else
                {
                        if(jishu==(n/2))
                        {
                                for(i=0,w=2,a=0; i<n; i++)
                                {
                                        if(f[i]==1)
                                        {
                                                if(i+1>w)a+=i+1-w;
                                                else a+=w-i-1;
                                                w=w+2;
                                        }
                                }
                                printf("%d\n",a);
                        }
                        else
                        {
                                for(i=0,w=1,a=0; i<n; i++)
                                {
                                        if(f[i]==1)
                                        {
                                                if(i+1>w)a+=i+1-w;
                                                else a+=w-i-1;
                                                w=w+2;
                                        }
                                }
                                printf("%d\n",a);
                        }
                }
        }
        return 0;
}

最佳答案

月排行榜 / 总排行榜

jackz007

2022-10-15 02:26:58

#include <stdio.h>

int main(void)
{
        int a , b , c , d[110][110] , i , j , k , p , q , r , t , x                      ;
        scanf("%d" , & t)                                                                ;
        for(i = 0 ; i < t ; i ++) {
                scanf("%d" , & d[i][0])                                                  ;
                for(j = 0 ; j < d[i][0] ; j ++) scanf("%d" , & d[i][j + 1])              ;
        }
        for(i = 0 ; i < t ; i ++) {
                for(a = b = j = 0 ; j < d[i][0] ; j ++) {
                        if(d[i][j + 1] % 2) a ++                                         ;
                        else b ++                                                        ;
                }
                for(c = j = 0 ; j < d[i][0] ; j += 2) if(d[i][j + 1] % 2) c ++           ;
                if(a > b && a - b < 2 || a < b && b - a < 2 || a == b) {
                        p = 0                                                            ;
                        q = 1                                                            ;
                        if(a < b || (a == b && 2 * c < a)) {
                                p = 1                                                    ;
                                q = 0                                                    ;
                        }
                        for(r = 0 ;;) {
                                for(j = p ; j < d[i][0] && d[i][j + 1] % 2 ; j += 2)     ;
                                for(k = q ; k < d[i][0] && ! (d[i][k + 1] % 2) ; k += 2) ;
                                if(j < d[i][0] && k < d[i][0]) {
                                        x = d[i][j + 1]                                  ;
                                        d[i][j + 1] = d[i][k + 1]                        ;
                                        d[i][k + 1] = x                                  ;
                                        r ++                                             ;
                                } else {
                                        break                                            ;
                                }
                        }
                        printf("%2d : %d" , r , d[i][1])                                 ;
                        for(j = 1 ; j < d[i][0] ; j ++) printf(",%d" , d[i][j + 1])      ;
                        printf("\n")                                                     ;
                } else {
                        printf("-1 :\n")                                                 ;
                }
        }
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
5
3
6 6 1
1
9
6
1 1 1 2 2 2
2
8 6
6
6 2 3 4 5 1
 1 : 6,1,6
 0 : 9
 1 : 1,2,1,2,1,2
-1 :
 1 : 1,2,3,4,5,6

D:\[00.Exerciese.2022]\C>

        这个结果和样例给出的答案有出入，特别是第 3 、5 组，第 3 组只要交换索引 1、4 的元素即可，只需要 1 次交换，第 5 组数据只要交换索引 0、5 的元素即可，也只要交换一次，从而，与样例答案有所不同，不知道这个理解是否正确。

跳转到最佳答案楼层

jackz007

#include <stdio.h>

int main(void)
{
        int a , b , c , d[110][110] , i , j , k , p , q , r , t , x                      ;
        scanf("%d" , & t)                                                                ;
        for(i = 0 ; i < t ; i ++) {
                scanf("%d" , & d[i][0])                                                  ;
                for(j = 0 ; j < d[i][0] ; j ++) scanf("%d" , & d[i][j + 1])              ;
        }
        for(i = 0 ; i < t ; i ++) {
                for(a = b = j = 0 ; j < d[i][0] ; j ++) {
                        if(d[i][j + 1] % 2) a ++                                         ;
                        else b ++                                                        ;
                }
                for(c = j = 0 ; j < d[i][0] ; j += 2) if(d[i][j + 1] % 2) c ++           ;
                if(a > b && a - b < 2 || a < b && b - a < 2 || a == b) {
                        p = 0                                                            ;
                        q = 1                                                            ;
                        if(a < b || (a == b && 2 * c < a)) {
                                p = 1                                                    ;
                                q = 0                                                    ;
                        }
                        for(r = 0 ;;) {
                                for(j = p ; j < d[i][0] && d[i][j + 1] % 2 ; j += 2)     ;
                                for(k = q ; k < d[i][0] && ! (d[i][k + 1] % 2) ; k += 2) ;
                                if(j < d[i][0] && k < d[i][0]) {
                                        x = d[i][j + 1]                                  ;
                                        d[i][j + 1] = d[i][k + 1]                        ;
                                        d[i][k + 1] = x                                  ;
                                        r ++                                             ;
                                } else {
                                        break                                            ;
                                }
                        }
                        printf("%2d : %d" , r , d[i][1])                                 ;
                        for(j = 1 ; j < d[i][0] ; j ++) printf(",%d" , d[i][j + 1])      ;
                        printf("\n")                                                     ;
                } else {
                        printf("-1 :\n")                                                 ;
                }
        }
}

        编译、运行实况：

D:\[00.Exerciese.2022]\C>g++ -o x x.c

D:\[00.Exerciese.2022]\C>x
5
3
6 6 1
1
9
6
1 1 1 2 2 2
2
8 6
6
6 2 3 4 5 1
 1 : 6,1,6
 0 : 9
 1 : 1,2,1,2,1,2
-1 :
 1 : 1,2,3,4,5,6

D:\[00.Exerciese.2022]\C>

        这个结果和样例给出的答案有出入，特别是第 3 、5 组，第 3 组只要交换索引 1、4 的元素即可，只需要 1 次交换，第 5 组数据只要交换索引 0、5 的元素即可，也只要交换一次，从而，与样例答案有所不同，不知道这个理解是否正确。