AcWing 1353. Ski resort design (greedy)

【 Title Description 】
Farmer John's farm has $N$ A mountain , The height of each mountain is an integer .
In winter , John often holds ski training camps on these mountains .
Unfortunately , From next year , The state will introduce a new tax law on ski resorts .
If the height difference between the highest peak and the lowest peak of the ski resort is greater than $17$, The state collects taxes .
To avoid paying taxes , John decided to trim the height of these peaks .
It is known that , Increase or decrease a mountain peak $x$ Unit height , Need to spend $x^2$ The money of .
John is only willing to change the height of integer units , And each peak can only be modified once .
Excuse me, , How much does John need to spend at least , Only then can the height difference between the highest peak and the lowest peak not be greater than $17$.

【 Input format 】
The first line contains integers $N$.
Next $N$ That's ok , Each line contains an integer , Indicates the height of a mountain .

【 Output format 】
Output an integer , Indicates the least money spent .

【 Data range 】
$1\le N\le 1000$
Data assurance , The initial height of each mountain is $0\sim 100$ Between .

【 sample input 】

5
20
4
1
24
21

【 sample output 】

18

【 Sample explanation 】
The best solution is , Set the height to $1$ The mountains of , increase $3$ One unit height , Set the height to $24$ The mountains of , Reduce $3$ One unit height .

【 analysis 】

---

Because the initial height of each mountain is $0\sim 100$ Between , Therefore, it is easy to prove that the height of the highest peak and the lowest peak must also be $0\sim 100$ In this range , That is, the height range is $0\sim 17,1\sim 18,\dots ,83\sim 100$ One of them . So we can enumerate each interval $[l,r]$, Calculate the height of all the peaks $h[i]$ The total cost of modifying to this range $cost$（ if $h[i]<l$ be $cost+(l-h[i]{)}^2$; if $h[i]>r$ be $cost+(h[i]-r{)}^2$）, Take the minimum value of all interval costs .

---

【 Code 】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1010;
int h[N];
int n;

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    int res = 0x3f3f3f3f;
    for (int l = 0; l + 17 <= 100; l++)
    {
    
        int r = l + 17, cost = 0;
        for (int i = 0; i < n; i++)
            if (h[i] < l) cost += pow(l - h[i], 2);
            else if (h[i] > r) cost += pow(h[i] - r, 2);
        res = min(res, cost);
    }
    cout << res << endl;
    return 0;
}