A great thinking problem cf1671d insert a progression

One . The question ：

  Here's a length of n Array of , Here are some numbers for you 1~x, Ask you to insert these numbers into the array （ It can be inserted at both ends of the array , It can also be inserted into the array ）, Make the sum of the absolute values of the differences between every two adjacent elements of the whole array minimum （ In fact, each element in the array is treated as a column of corresponding height , This value is the total number of steps from the first column to the last column , This value is hereinafter referred to as sum） Please find a way to insert , Then output the minimum sum.

Two . Ideas ：

If the element range of the existing array is l~r that ,l~r The insertion position can be found in the array , And do not change the original array sum,（ If you want to insert x, As long as there is a position pos One element on both sides of this position is less than x One is greater than x that will do , This will not increase sum, Because this is actually a step paved between the two positions , I didn't go up or down more ）, that 1~l-1, and r+1~x What about these numbers ？ In fact, we can 1~l-1 These figures are regarded as 1 That's it , Because all the elements in the original array must be better than 1 Big , So no matter 1 where , There will be a downhill road and an uphill road to go , In fact, it increases the number of steps （sum）, And lay in between “ steps ” It doesn't increase sum, For example, now there are two numbers 2 3 We put 1 Insert it 4 1 5  Now 21 It's downhill ,1 3 It's uphill , Originally from 2 To 3 Just go 1 Step , Now go more 6 Step , And if the Take the rest 2 3 Insert it as a step , Then it will become 4 3 2 1 5 So follow the steps to 1 It will not increase any steps , perhaps 4 1 2 3 5 Follow the steps to 5 It won't increase any steps , So just think about 1 The position of , At this point, we iterate through each put 1 The location of , Then calculate how much it will increase sum that will do .r+1~x Empathy , Think as a whole x that will do .

3、 ... and . Code

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2E5+10;
int a[N];
typedef long long LL;
void solve()
{
    int n,x;
    cin>>n>>x;
    int maxx=0;
    int minn=0x3f3f3f3f;
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        ans+=max(a[i+1]-a[i],a[i]-a[i+1]);// Of the initial array sum
        maxx=max(maxx,a[i]);
        minn=min(minn,a[i]);
    }
    if(maxx<x)
    {
        int minw=0x3f3f3f3f;
        for(int i=1;i<n;i++)
        {
            minw=min(minw,x-a[i]+x-a[i+1]-abs(a[i]-a[i+1]));// Here is the minimum value of the increase. Don't forget to subtract the original steps 
        }
        minw=min(minw,min(x-a[1],x-a[n]));
        ans+=minw;
        
    }
    if(minn>1)
    {
        int minw=0x3f3f3f3f;
        for(int i=1;i<n;i++)
        {
            minw=min(minw,a[i]-1+a[i+1]-1-abs(a[i]-a[i+1]));
        }
        minw=min(minw,min(a[1]-1,a[n]-1));
        ans+=minw;
    }
    cout<<ans<<endl;
    
    
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}