洛谷：P2882：Face The Right Way

题目

P2882：Face The Right Way

分析

一个直观的解法是：对于某个特定的k，从头遍历所有的N头牛，对每一个位置i根据朝向进行翻转判定。如果需要翻转，那么还需要对这个区间的其他牛的朝向进行翻转。这将记为一次操作。这个操作需要遍历所有的k，所有的N头牛，且对k区间里的牛进行翻转，时间复杂度来到\(O(N^3)\)，极限状态下会超时。

从上述分析可以看出，我们要对一个区间进行连续的相同的操作（加1次翻转）。这是应用差分的提示。

而某一头牛最终的朝向，由初始朝向和翻转次数决定。而有了差分后，某个位置的牛总共翻转了几次也可以通过前缀和快速得到，不需要用一个巨大的数组每次跟踪。

判定、差分、前缀和的联合

int solve(int N, int K, const vector<int>& cows)
{
    vector<int> state = cows;    // 复制原始状态
    vector<int> diff(N + 1, 0);  // 差分数组，记录翻转操作
    int operations = 0;
    int flip_count = 0;  // 当前位置受到的翻转次数

    for (int i = 0; i < N; i++)
    {
        // 更新当前位置的翻转次数
        flip_count += diff[i];

        // 计算当前牛的实际朝向（原始朝向 + 翻转次数的奇偶性）
        int current_direction = (state[i] + flip_count) % 2;

        // 如果当前牛朝后(0)，需要翻转
        if (current_direction == 0)
        {
            // 检查是否能进行K长度的翻转
            if (i + K > N)
            {
                return INT_MAX;  // 无法完成翻转
            }

            // 使用差分数组记录翻转操作：[i, i+K) 区间翻转
            diff[i]++;
            diff[i + K]--;
            flip_count++;  // 当前位置立即受到翻转影响
            operations++;
        }
    }

    return operations;
}

通过差分，我们将\(O(N^3)\)的时间复杂度降到了\(O(N^2)\)。根据题意，\(N\le 5000\)，所以是可以通过的。

答案

思考

（略）