【推导】Codeforces Round #402 (Div. 2) A. Pupils Redistribution

一次交换,会让Group A里面的某个数字的数量-1,另一个数字的数量+1;对Group B恰好相反。

于是答案就是xigma(i=1~5,numA[i]-numB[i]>0)(numA[i]-numB[i])/2,如果这个值无法被2整除,则无解,或者如果这个值不等于xigma(i=1~5,numA[i]-numB[i]<0)(-numA[i]+numB[i])/2的话,也无解。

或者如果某个值在两组中出现的总次数无法被2整除,也无解。

#include<cstdio>
using namespace std;
int n,a[110],b[110],num[11],A,B,num2[11];
int main()
{
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
	  scanf("%d",&b[i]);
	for(int i=1;i<=n;++i)
	  ++num[a[i]];
	for(int i=1;i<=n;++i)
	  ++num2[b[i]];
	for(int i=1;i<=5;++i)
	  if((num[i]+num2[i])%2==1)
	    {
	      puts("-1");
	      return 0;
	    }
	for(int i=1;i<=5;++i)
	  if(num[i]-num2[i]<0)
	    A+=(-num[i]+num2[i]);
	  else
	    B+=(num[i]-num2[i]);
	if(A!=B || A%2!=0)
	  {
	  	puts("-1");
	  	return 0;
	  }
	printf("%d
",A/2);
	return 0;
}
原文地址:https://www.cnblogs.com/autsky-jadek/p/6445542.html