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

灯火阑珊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

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int a , b , c , d[110][110] , i , j , k , p , q , r , t , x                      ;
   
6.         scanf("%d" , & t)                                                                ;
   
7.         for(i = 0 ; i < t ; i ++) {
   
8.                 scanf("%d" , & d[i][0])                                                  ;
   
9.                 for(j = 0 ; j < d[i][0] ; j ++) scanf("%d" , & d[i][j + 1])              ;
   
10.         }
    
11.         for(i = 0 ; i < t ; i ++) {
    
12.                 for(a = b = j = 0 ; j < d[i][0] ; j ++) {
    
13.                         if(d[i][j + 1] % 2) a ++                                         ;
    
14.                         else b ++                                                        ;
    
15.                 }
    
16.                 for(c = j = 0 ; j < d[i][0] ; j += 2) if(d[i][j + 1] % 2) c ++           ;
    
17.                 if(a > b && a - b < 2 || a < b && b - a < 2 || a == b) {
    
18.                         p = 0                                                            ;
    
19.                         q = 1                                                            ;
    
20.                         if(a < b || (a == b && 2 * c < a)) {
    
21.                                 p = 1                                                    ;
    
22.                                 q = 0                                                    ;
    
23.                         }
    
24.                         for(r = 0 ;;) {
    
25.                                 for(j = p ; j < d[i][0] && d[i][j + 1] % 2 ; j += 2)     ;
    
26.                                 for(k = q ; k < d[i][0] && ! (d[i][k + 1] % 2) ; k += 2) ;
    
27.                                 if(j < d[i][0] && k < d[i][0]) {
    
28.                                         x = d[i][j + 1]                                  ;
    
29.                                         d[i][j + 1] = d[i][k + 1]                        ;
    
30.                                         d[i][k + 1] = x                                  ;
    
31.                                         r ++                                             ;
    
32.                                 } else {
    
33.                                         break                                            ;
    
34.                                 }
    
35.                         }
    
36.                         printf("%2d : %d" , r , d[i][1])                                 ;
    
37.                         for(j = 1 ; j < d[i][0] ; j ++) printf(",%d" , d[i][j + 1])      ;
    
38.                         printf("\n")                                                     ;
    
39.                 } else {
    
40.                         printf("-1 :\n")                                                 ;
    
41.                 }
    
42.         }
    
43. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 5
   
5. 3
   
6. 6 6 1
   
7. 1
   
8. 9
   
9. 6
   
10. 1 1 1 2 2 2
    
11. 2
    
12. 8 6
    
13. 6
    
14. 6 2 3 4 5 1
    
15. 1 : 6,1,6
    
16. 0 : 9
    
17. 1 : 1,2,1,2,1,2
    
18. -1 :
    
19. 1 : 1,2,3,4,5,6
    
20. 
    
21. D:\[00.Exerciese.2022]\C>

复制代码

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

跳转到最佳答案楼层

jackz007

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int a , b , c , d[110][110] , i , j , k , p , q , r , t , x                      ;
   
6.         scanf("%d" , & t)                                                                ;
   
7.         for(i = 0 ; i < t ; i ++) {
   
8.                 scanf("%d" , & d[i][0])                                                  ;
   
9.                 for(j = 0 ; j < d[i][0] ; j ++) scanf("%d" , & d[i][j + 1])              ;
   
10.         }
    
11.         for(i = 0 ; i < t ; i ++) {
    
12.                 for(a = b = j = 0 ; j < d[i][0] ; j ++) {
    
13.                         if(d[i][j + 1] % 2) a ++                                         ;
    
14.                         else b ++                                                        ;
    
15.                 }
    
16.                 for(c = j = 0 ; j < d[i][0] ; j += 2) if(d[i][j + 1] % 2) c ++           ;
    
17.                 if(a > b && a - b < 2 || a < b && b - a < 2 || a == b) {
    
18.                         p = 0                                                            ;
    
19.                         q = 1                                                            ;
    
20.                         if(a < b || (a == b && 2 * c < a)) {
    
21.                                 p = 1                                                    ;
    
22.                                 q = 0                                                    ;
    
23.                         }
    
24.                         for(r = 0 ;;) {
    
25.                                 for(j = p ; j < d[i][0] && d[i][j + 1] % 2 ; j += 2)     ;
    
26.                                 for(k = q ; k < d[i][0] && ! (d[i][k + 1] % 2) ; k += 2) ;
    
27.                                 if(j < d[i][0] && k < d[i][0]) {
    
28.                                         x = d[i][j + 1]                                  ;
    
29.                                         d[i][j + 1] = d[i][k + 1]                        ;
    
30.                                         d[i][k + 1] = x                                  ;
    
31.                                         r ++                                             ;
    
32.                                 } else {
    
33.                                         break                                            ;
    
34.                                 }
    
35.                         }
    
36.                         printf("%2d : %d" , r , d[i][1])                                 ;
    
37.                         for(j = 1 ; j < d[i][0] ; j ++) printf(",%d" , d[i][j + 1])      ;
    
38.                         printf("\n")                                                     ;
    
39.                 } else {
    
40.                         printf("-1 :\n")                                                 ;
    
41.                 }
    
42.         }
    
43. }

复制代码

        编译、运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 5
   
5. 3
   
6. 6 6 1
   
7. 1
   
8. 9
   
9. 6
   
10. 1 1 1 2 2 2
    
11. 2
    
12. 8 6
    
13. 6
    
14. 6 2 3 4 5 1
    
15. 1 : 6,1,6
    
16. 0 : 9
    
17. 1 : 1,2,1,2,1,2
    
18. -1 :
    
19. 1 : 1,2,3,4,5,6
    
20. 
    
21. D:\[00.Exerciese.2022]\C>

复制代码

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