CF1556B Take Your Places!

Link

洛谷 & Codeforces

Tag

洛谷：暂无标签

Codeforces：implementation

Difficulty Level

洛谷：$普及-$

Codeforces： $1300$

Solution

首先判断是否可能。显然奇数个数与偶数个数最多相差 $1$，当且仅当 $a_1$ 和 $a_n$ 的奇偶性相同时相差 $1$，而相差不大于 $1$ 时一定有方法能够使得任意两个相邻的元素奇偶性不同，因此当且仅当奇偶之差大于 $1$ 时不可能。

当奇偶个数不同时， $a_1$ 的奇偶性已经确定为数量较多的一种，因此操作结束后的序列的所有位置的奇偶性都确定；当奇偶个数相同时，$a_1$ 的奇偶性不确定，因此最终序列的奇偶性有两种可能。

对于一个奇偶性确定的最终序列，我们可以得到最优方案：将原序列第一个奇数（偶数）移到最终序列第一个奇数（偶数），将原序列第二个奇数（偶数）移到最终序列第二个奇数（偶数），以此类推，即使奇数（偶数）之间的先后顺序不变。

显然，我们只需将奇数和偶数中的一种排列好，另一种也已排好，因此只需统计一种的答案即可。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
LL n,num1,num0;
LL a[100010];
LL ans=0x3f3f3f3f3f3f3f3fll;
void work()
{
	ans=0x3f3f3f3f3f3f3f3fll;
	num1=num0=0;
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]%=2;
		num1+=a[i];
		num0+=!a[i];
	}
	if(abs(num1-num0)>1)
	{
		printf("-1\n");
		return;
	}
	if(num1>=num0)
	{
		LL pos=1,s=0;
		for(LL i=1;i<=n;i++)
			if(a[i])
			{
				s+=abs(pos-i);
				pos+=2;
			}
		ans=min(ans,s);
	}
	if(num1<=num0)
	{
		LL pos=1,s=0;
		for(LL i=1;i<=n;i++)
			if(!a[i])
			{
				s+=abs(pos-i);
				pos+=2;
			}
		ans=min(ans,s);
	}
	printf("%lld\n",ans);
}
int main()
{
	LL T;
	scanf("%lld",&T);
	while(T--)
		work();
	return 0;
}

Submission

Codeforces submission