21xrx.com
2024-12-27 20:33:00 Friday
登录
文章检索 我的文章 写文章
C++ 分糖果题解
2023-06-28 04:05:06 深夜i     --     --
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上调。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复