|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
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:37 编辑 #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 的元素即可，也只要交换一次，从而，与样例答案有所不同，不知道这个理解是否正确。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-10-14 22:05:25
置顶卡
千斤顶
显身卡