贪心算法简单讲讲_C/C++

贪心算法：贪心算法是我们在试题过程之中经常遇见的一种算法，但是每次看到贪心算法的时候我们总会有一种知道但是确抓不住的感觉有没有？相信大部分人一开是都是这种感觉。往往想去证明一个贪心算法并且得到贪心算法的一般解题过程和公式.......其实啊，贪心算法是一种思路，就是用局部最优解来推的全局最优解，简而言之就是用局部最优推全局最优。一般想要这类思路的题目没有什么固定的套路，这就需要我们仔细去发寻这个“贪”到底“贪”在哪。用比较官方的话解释就是心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望能够导致全局最优解的算法。贪心算法对于解决一些最优化问题非常有效，但并不是所有问题都适合使用贪心算法。在应用贪心算法时，需要确保问题具有贪心选择性质和最优子结构性质，以确保贪心算法得到的局部最优解能够导致全局最优解。

其实对于贪心算法的概念是比较好理解的，主要是在运用中发现贪心算法的精妙之处：下面是一道举例的贪心题~

读完题目，咱们发现这个题目想要砍竹子，得到最少的次数是不是想要保证尽可能多高度相同的竹子一起砍，那有怎么确定顺序呢？结果是很明显的，我尽可能先找到最高的砍了，（根据那个公式哈）这样发现后面基本上会得到多个相同的。

确定了贪心思路咱们就可以开始码题了

首先我们写一个怎么砍竹子的函数，根据题目的意思可以很明确的看出是向下取整就行了

signed kan(int h){
	return (int)(sqrtl(h/2+1));
}

然后在主函数里面我定义一个数组a来表示一颗竹子我需要看多少次才能得到我想要的结果里面使用了一个递归。

后面对竹子进行遍历，找到最高的竹子之后，发现有一样高度的就一起进行操作，不然就单独对那颗比较高的竹子进行操作。

signed main(){
	cin>>n;
	vector<int> h(n+1);
	vector<int> a(n+1);
	for(int i=1;i<=n;i++){
		cin>>h[i];
		ans=h[i];
		while(ans-1){
			a[i]++;
			ans=kan(ans);
		}
		maxn=max(maxn,a[i]);
	}
	for(int i=maxn;i>=1;i--){
		for(int j=1;j<=n;j++){
			if(a[j]==i){		
			    if(h[j]!=h[j+1]) counts++;
				a[j]--;
				h[j]=kan(h[j]);
			}
		}
	
	cout<<counts<<endl;
	return 0;
}

常规定义一下初始变量我们可以得到完整的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int maxn=-100000;
int ans=0;
int counts=0;
signed kan(int h){
	return (int)(sqrtl(h/2+1));
}
signed main(){
	cin>>n;
	vector<int> h(n+1);
	vector<int> a(n+1);
	for(int i=1;i<=n;i++){
		cin>>h[i];
		ans=h[i];
		while(ans-1){
			a[i]++;
			ans=kan(ans);
		}
		maxn=max(maxn,a[i]);
	}
	for(int i=maxn;i>=1;i--){
		for(int j=1;j<=n;j++){
			if(a[j]==i){		
			    if(h[j]!=h[j+1]) counts++;
				a[j]--;
				h[j]=kan(h[j]);
			}
		}
	
	cout<<counts<<endl;
	return 0;
}

这样一个根据贪心的思路问题咱就解决啦！