洛谷：P1824：进击的奶牛

题目

P1824：进击的奶牛

分析

这道题是复合题：要用到“二分”和“贪心”。

贪心算法的核心在于：假定目前的放置距离是d，那么以此距离——可以超过这个距离，因为牛棚的位置不是连续的——放牛，看看能否达到题目要求。

其代码如下：

bool canPlaceCows(const vector<int>& stalls, int C, int d)
{
    int count = 1;                  // 放置第一头牛
    int last_position = stalls[0];  // 第一头牛的位置

    for (int i = 1; i < stalls.size(); ++i)
    {
        if (stalls[i] - last_position >= d) //第i个位置可以放一头牛
        {
            count++;                    
            last_position = stalls[i];  // 更新最后放置的位置
            if (count == C) // 成功放置所有牛
            {
                return true;  
            }
        }
    }
    return false;  // 无法放置所有牛
}

二分算法的核心在于：我们不知道合理的d是多少，但直觉告诉我们d总有个上限——超过这个上限后就肯定放不下了。所以很适合用二分法。

其代码如下：

    while (left <= right)
    {
        int mid = left + (right - left) / 2;  // 当前尝试的最小距离
        if (canPlaceCows(stalls, C, mid))
        {
            result = mid;    // 更新结果
            left = mid + 1;  // 尝试更大的最小距离
        }
        else
        {
            right = mid - 1;  // 尝试更小的最小距离
        }
    }

答案

思考

这道题目不难，但我还是放在这里，因为它有几个值得关注的地方：

1. 结合了“二分”和“贪心”，而贪心是核心，二分作为辅助的手段。
2. 但是，这题贪心的策略简单，而二分的策略需要有一些额外的考量。