题目描述
给定一个长度为 $n$ 的正整数数组 $A$，其中所有数从左至右排成一排。
你需要将每个位置染成一种颜色，使得任意相邻两个位置的颜色不同。请计算最少需要多少种颜色，或者在给定颜色数量限制下判断是否可行。
解题思路
本题属于图论中的着色问题在一维数组上的简化应用。对于一维数组而言，只要保证相邻元素颜色不同即可。根据贪心策略，第一个元素可以任选一种颜色，后续每个元素只需选择与前一元素不同的任意一种颜色。因此，对于长度大于 1 的数组，最少需要 2 种颜色；若数组长度为 1，则只需要 1 种颜色。
如果题目涉及更复杂的约束（如特定位置颜色固定、颜色成本不同等），则需要使用动态规划或最小费用流等算法求解。但在基础 CSP-S 难度下，通常考察对贪心策略的理解及边界情况的处理。
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
if (!(cin >> n)) return 0;
if (n == 0) {
cout << 0 << endl;
return 0;
}
// 基础情况：至少需要 1 种颜色
// 若存在相邻元素，则至少需要 2 种颜色
if (n > 1) {
cout << 2 << endl;
} else {
cout << 1 << endl;
}
return 0;
}
总结
解决此类问题的关键在于识别约束条件。对于简单的相邻不同色问题，贪心法是最优解。在实际竞赛中，需注意输入规模带来的时间复杂度要求，以及特殊边界值（如 $n=1$）的处理。
