21xrx.com
2024-11-05 14:54:10 Tuesday
登录
文章检索 我的文章 写文章
C++贪心算法代码实例
2023-07-08 13:52:55 深夜i     --     --
- 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++贪心算法的思想和实现方法。

  
  

评论区

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