思维题
思路
自己想到了一点点思路但是不足以解决整个问题,所以还是看别人的吧
见: https://zhuanlan.zhihu.com/p/405446140
代码
知乎大佬的代码比我自己写的代码好太多了…
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,a[N];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
int odd_num=0,even_num=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x%2==1)
odd_num++;
else
even_num++;
a[i]=x;
}
if(abs(odd_num-even_num)>1)
cout<<-1<<endl;
else if(odd_num-even_num==1)
{
int res=0;
int last=1;
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
res+=abs(i-last);
last+=2;
}
}
cout<<res<<endl;
}
else if(even_num-odd_num==1)
{
int res=0;
int last=1;
for(int i=1;i<=n;i++)
{
if(a[i]%2==0)
{
res+=abs(i-last);
last+=2;
}
}
cout<<res<<endl;
}
else if(even_num==odd_num)
{
int res1=0,res2=0;
int last1=1,last2=1;
for(int i=1;i<=n;i++)
{
if(a[i]%2==0)
{
res1+=abs(i-last1);
last1+=2;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
res2+=abs(i-last2);
last2+=2;
}
}
cout<<min(res1,res2)<<endl;
}
}
return 0;
}