圣诞节快到了，小 Q 买了一列共 n 个彩灯，且彩灯的编号是一个 1~n 的排列。 现在某些彩灯被摘下去了，小 Q 要把这些灯重新挂上去。 小 Q 不记得原来的顺序是什么样子了。但他希望彩灯挂上去之后，相邻彩灯的奇偶性尽可能相同。 也即，奇偶性不同的相邻彩灯尽可能少。那么重新挂上去之后，最少多少对奇偶性不同的相邻彩灯呢？c++代码

以下是一个可能的 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> lights(n);
    for (int i = 0; i < n; i++) {
        cin >> lights[i];
    }

    // dp[i][0] 表示前 i 个彩灯中，以奇数结尾的最少奇偶性不同的相邻彩灯对数
    // dp[i][1] 表示前 i 个彩灯中，以偶数结尾的最少奇偶性不同的相邻彩灯对数
    vector<vector<int>> dp(n, vector<int>(2, 0));
    if (lights[0] % 2 == 1) {
        dp[0][0] = 0;
        dp[0][1] = 1;
    } else {
        dp[0][0] = 1;
        dp[0][1] = 0;
    }

    for (int i = 1; i < n; i++) {
        if (lights[i] % 2 == 1) {
            dp[i][0] = dp[i-1][1]; // 前一个是偶数结尾
            dp[i][1] = dp[i-1][0] + 1; // 前一个是奇数结尾
        } else {
            dp[i][0] = dp[i-1][0] + 1; // 前一个是奇数结尾
            dp[i][1] = dp[i-1][1]; // 前一个是偶数结尾
        }
    }

    cout << min(dp[n-1][0], dp[n-1][1]) << endl;

    return 0;
}

该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。