每日一题之干草堆的移动

经典的贪心分析：

先上题目题目：

 

初看题目一想想比较复杂，    挺难考虑 ， 但其实画画图找找规律，发现其实也还比较容易模拟。

首先最关键是要抓住一个重点：（每一个干草堆都要变成相同的值。。）。

所以要考虑的就是这个相同的值应该是什么，其实模拟几遍发现就是它的平均值：：简简单单的画个图：

可以分为高的甘草堆和矮的干草堆。。。可以采用贪心分析：：：

假如说有一个干草堆高度太高了，那么他就可以给那些比较矮的干草堆赠送干草，赠送多少呢，使得自己的干草堆变成相同的那个平均数即可。赠送给哪个比较矮的干草堆呢，我们不管，赠送出去，送给空气。反正我赠送出去了，这些干草堆反正都是矮干草的，又不会丢。

你也许会问：这样赠送出去就能保证所有高度相等吗？答案是肯定的，一个比较高的干草堆赠送之后，高度会变成平均数。所有高的干草堆赠送之后，所有高度肯定相等

因此事情就变得简单了，，直接上代码即可

 

//贪心先分析
#include<iostream>
#include<algorithm>
const int N = 1e5 +10;
int a[N];
 
using namespace std;
int main()
{
     int n ;
     cin>>n;
     int sum = 0 , cnt = 0;
    
     for(int i=0; i<n; i++)
     {
         cin>>a[i];
         sum += a[i];
     }
     
     int hh = sum / n;
     
     for(int i=0; i<n; i++)
     {
         if(a[i] < hh )  cnt += hh - a[i];
         
     }
     cout << cnt<< endl;
     return 0;
      
}

 关于贪心的一些知识

百度百科解释：：贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。。

贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题： [5] 

1、该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质 [5]  ；

2、制定贪心策略，以达到问题的最优解或较优解 [5]  。

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解 [5]  。