题解 | #最小连通代价#

题意：同奇偶连线代价为a,不同奇偶连线代价为b,求n个点连线的最小代价【注意a和b可以<=0】

思路： 很明显我们可以手绘出两层

奇数： x x x x

偶数： x x x x x

开始分类讨论【注意奇数或偶数的个数为0的情况，就必须只能同类连线】：

1.若a<0,b<0：连的线越多越好 同类两两连线，不同类也两两连线

2.若a<0,b>=0 或 a>0,b<=0:同类全都连线，不同奇偶类间连一条线

3.若a>0,b>0:分类如果a<b则同类连线，不同类连一根；若b<a，则不同类之间连线

void solve()
{
	int n, a, b;
	cin >> n >> a >> b;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		if (num % 2)
			cnt1++;
		else
			cnt2++;
	}
	int na = 0, nb = 0;
	if (a <= 0 && b <= 0)
	{
		na = cnt1 * (cnt1 - 1) / 2 + (cnt2) * (cnt2 - 1) / 2;
		nb = cnt1 * cnt2;
	}
	else if (a <= 0 && b > 0)
	{
		na = cnt1 * (cnt1 - 1) / 2 + cnt2 * (cnt2 - 1) / 2;
		if (cnt1 && cnt2)
			nb = 1;
	}
	else if (a > 0 && b <= 0)
	{
		if (cnt1 && cnt2)
			nb = cnt1 * cnt2, na = 0;
		else
			na = n - 1, nb = 0;
	}
	else if (a > 0 && b > 0)
	{
		if (cnt1 && cnt2)
		{
			if (a < b)
				nb = 1, na = n - 2;
			else
				nb = n - 1, na = 0;
		}
		else
		{
			nb = 0, na = n - 1;
		}
	}
	int ans = 0;
	ans = a * na + b * nb;
	cout << ans << endl;
}