21xrx.com
2025-03-24 16:15:37 Monday
文章检索 我的文章 写文章
C++ 分糖果题解
2023-06-28 04:05:06 深夜i     11     0
C++编程 分糖果问题 算法 贪心思想 代码分析

在这个题目中，我们需要将一定数量的糖果分给一定数量的小朋友，每个小朋友需要至少获得一个糖果。题目中要求我们最小化糖果数的最大值。

由于要最小化糖果数的最大值，这个问题可以看作二分答案问题。假设现在我们猜测答案为x，那么我们可以通过贪心的思路来判断是否可行：

1. 首先将每个小朋友的需求值设置为1；

2. 从需求值最小的小朋友开始，将当前拥有的糖果数分给该小朋友，直到该小朋友的需求值为x或者糖果数用完为止；

3. 如果所有小朋友的需求值都为x，说明当前猜测的答案可行，我们可以将猜测答案下调；

4. 否则说明当前猜测的答案不可行，我们需要将猜测答案上调。

下面是代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int l = 1, r = 1e9, ans = 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    int now = 0;
    for (int i = 0; i < n; i++) {
      if (now + a[i] <= mid) {
        now += a[i];
      } else {
        now = a[i];
        m--;
        if (m == 0) break;
      }
    }
    if (m == 0)
      ans = mid;
      r = mid - 1;
     else {
      l = mid + 1;
    }
  }
  cout << ans << endl;
  return 0;
}

在上面的代码中，l和r分别表示二分答案的下限和上限，ans表示当前可行的答案。我们通过一个while循环不断二分答案，找到最小的ans使得问题有解。在循环中，首先计算中间值mid，然后使用贪心的思路模拟糖果分配的过程，最后判断当前二分的范围。如果m == 0，说明当前mid可行，我们将ans更新为mid，并将r下调。否则，我们需要向更大的答案猜测，将l上调。

  
  

评论区