21xrx.com
2025-06-30 22:54:13 Monday
文章检索 我的文章 写文章
C++贪心算法代码实例
2023-07-08 13:52:55 深夜i     20     0
- C++ - 贪心算法 - 代码实例 - 算法实现 - 优化策略

贪心算法是一种经典的算法思想，它常用于求解最优解问题。在计算机科学中，C++语言是一种非常流行的编程语言，它有着强大的编程能力和易于使用的特点。本文将为您介绍C++贪心算法的实例代码。

一、C++贪心算法简介

贪心算法是一种非常常用的算法思想。它的核心思想是，在问题的每一步中都选择最优解，这样的选择会最终得到全局最优解。因此，贪心算法通常适用于局部最优解就可以导致全局最优解的情况。贪心算法具有简单、高效的特点。对于一些不是非常复杂的问题，贪心算法可以很好地解决，且计算量不大。

二、C++贪心算法实例代码

接下来，我们将为您提供两个C++贪心算法的实例代码，以便更好地理解此算法。

例1：糖果问题

假设有N个孩子和M个糖果，你可以将每个孩子分配不同数量的糖果。然而，给定的糖果的数量是有限制的，一些孩子可能分配不到糖果。现在请你实现一个函数，输出可以得到糖果的最大值。其中，第一个输入参数表示孩子的数量，第二个输入参数表示糖果的数量，第三个输入参数表示一个vector，存储了每个孩子希望得到的糖果数量。

#include<bits/stdc++.h>
using namespace std;
int findContentChildren(int n, int m, vector<int>& candy) {
  sort(candy.begin(), candy.end());
  int ans = 0, index = 0;
  for(int i = 0; i < n && index < m; i++){
    if(candy[index] <= i){
      ans++;
      index++;
    }
  }
  return ans;
}
int main(){
  int n, m;
  cin>>n>>m;
  vector<int> candy(n, 0);
  for(int i = 0; i < n; i++){
    cin>>candy[i];
  }
  cout<<findContentChildren(n, m, candy)<<endl;
  return 0;
}

例2：游戏问题

现在有一个长度为N的非负整数数组，您的任务是通过N次操作，将这个数组中的所有数都变成0。每次操作可以将其中一个数减去1，也可以将其中的一个数变成0。请输出需要的最少操作次数。

#include<bits/stdc++.h>
using namespace std;
int minimumMoves(vector<int>& nums) {
  int n = nums.size(), ans = 0;
  for(int i = 0; i < n; i++){
    if(nums[i] != 0){
      int j = i;
      while(j < n && nums[j] != 0) j++;
      ans += (j - i + 1) / 2;
      i = j;
    }
  }
  return ans;
}
int main(){
  int n;
  cin>>n;
  vector<int> nums(n, 0);
  for(int i = 0; i < n; i++){
    cin>>nums[i];
  }
  cout<<minimumMoves(nums)<<endl;
  return 0;
}

三、总结

C++贪心算法是一种非常好的算法思想，它可以用来解决一些不是非常复杂的问题。在使用C++贪心算法时，我们需要明确问题的每一步操作，并选择最优解，从而得到全局最优解。通过上面介绍的两个实例代码，我们可以发现C++贪心算法的代码写起来很简单，而且计算量也不大。希望这篇文章可以帮助到您，理解C++贪心算法的思想和实现方法。

  
  

评论区