Daily topic: movement of haystack

Classic greedy analysis ：

Let's start with the topic ：

 

At first glance, the topic is more complex ,    It's hard to think about , But in fact, draw pictures to find rules , In fact, it is easy to simulate .

First of all, the key is to grasp a key point ：（ Every haystack should become the same value ..）.

So what to consider is what the same value should be , In fact, the average value is found after several simulations ：： Simply draw a picture ：

It can be divided into high licorice piles and low haystacks ... Greedy analysis can be used ：：：

If there is a haystack too high , Then he can give hay to those shorter haystacks , How much is the gift , Make your haystack the same average . Which shorter haystack will you give it to , We don't care , Give it away , Send air . Anyway, I gave it away , These haystacks are short hay anyway , It won't be lost .

You may ask ： Can you guarantee that all the height is equal if you give it away like this ？ The answer is yes , After a relatively high haystack is presented , The height will become an average . After all the high haystacks are presented , All heights must be equal

So things become simple ,, Just go directly to the code

 

// Greedy first analysis 
#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;
      
}

  Some knowledge about greed

Baidu Encyclopedia explains ：： Greedy algorithm is a simpler solution to some problems 、 Faster design technology . Greedy algorithm is characterized by step by step , It is often based on the current situation and makes the optimal choice according to an optimization measure , Regardless of the possible overall situation , It saves a lot of time that must be spent trying everything possible to find the optimal solution . The greedy algorithm adopts top-down , Make successive greedy choices in an iterative way , Every greedy choice , The problem is reduced to a smaller subproblem , Through every step of greedy choice , An optimal solution of the problem can be obtained . Although it is necessary to ensure that the local optimal solution can be obtained at each step , However, the resulting global solution is sometimes not necessarily optimal , So greedy algorithms don't go back ..

Greedy algorithm does not consider the overall optimization , What is made is only a local optimal choice in a sense . When using greedy strategy, we should pay attention to the relationship between local optimization and global optimization , Choosing the current local optimum does not necessarily deduce the global optimum of the problem . Greedy strategy needs to solve the following two problems ： [5] 

1、 Is this problem suitable to be solved by greedy strategy , That is, whether the problem has the nature of greedy choice  [5]  ;

2、 Develop greedy strategies , To achieve the optimal solution or better solution of the problem  [5]  .

To determine whether a problem is suitable for solving with greedy algorithm , It must be proved that the greedy choice made at each step leads to the global optimal solution of the problem . The approximate process of proof is ： Firstly, a global optimal solution of the problem is investigated , It is proved that the optimal solution can be modified , Make it start with greedy choices , After making greedy choices , The original problem is simplified to a similar subproblem with smaller scale . And then use Mathematical induction Prove that you make greedy choices through every step , Finally, the overall optimal solution of the problem can be obtained  [5]  .