题目描述

小学生的高桥君很喜欢条纹图案. 现在, 高桥正在眺望从左到右排列在一条直线上的 nn 张彩色图画纸. 高桥非常喜欢条纹图案, 所以想通过用颜料把一些图画纸涂成新的颜色, 使其从整体上看是条纹图案.

从整体上看是条纹图案是指全部图画纸使用的颜色正好为 2 种, 且所有的图画纸的颜色与其相邻的图画纸不同.

你的任务是, 在给定已经配置好的图画纸的张数 nn 和把 1 张图画纸换成其他颜色所需的颜料的费用 cc 的基础上, 编制一个程序来输出达成条纹图案所需的总费用的最小值. 为了简化问题,图画纸上的每种颜色都是以 1 ~ 10 中的整数形式给出的. 可以用来重凃的颜料的颜色也只有这 10 种.

思路

题目中指出“条纹”，即“121212”或“010”这样的相邻两个数不相等，而且对于这个数列里的数，a[i]=a[i+2]。 那这里要判断，这条纹里的“颜色”需要哪两种。 所以，就有以下“贪心”策略： 枚举“条纹”里的奇数项，找到出现频率最高的颜色，将其他颜色转为这个颜色，偶数项也一样。 但这里有一个特例，即奇数项出现频率最高的与偶数项出现频率最高的相等，即样例二“1 1 1 1”，这样的话，答案就错了，所以，我们在判断偶数时，就需要特判。

代码

#include <bits/stdc++.h>
using namespace std;
int a[50000],cnt[30];
int main() {
	int n,m,s1=0,maxn=0,ans=0,maxk=0;
	cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i+=2) cnt[a[i]]++,s1++; //奇数项的数用桶装起来，判断出现频率
	for(int i=1; i<=10; i++)
		if(maxn<cnt[i]) maxn=cnt[i],maxk=i;//找出最大值

	ans=s1-maxn;//判断需要染几个数
	maxn=0;
	memset(cnt,0,sizeof(cnt));
	for(int i=2; i<=n; i+=2) cnt[a[i]]++;	//偶数项的数用桶装起来，判断出现频率
	for(int i=1; i<=10; i++) {
		if(i!=maxk)//判断是否与奇数项最高频率数相同
			if(maxn<cnt[i])
				maxn=cnt[i];
	}
	ans+=n-s1-maxn;//判断需要染几个数
	cout<<ans*m;//输出，记得乘m
	return 0;
}

暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n, m, ans = 1919810;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= 10; i ++)
		for (int j = 1; j <= 10; j ++)
			if (i != j) {
				int sum = 0;
				for (int k = 1; k <= n; k ++)
					if (a[k] != (k % 2 ? i : j))
						sum += m;
				ans = min(ans, sum);
			}
	cout << ans << '\n';
	return 0;
}