很棒的一个思维题CF1671D Insert a Progression

一.题意：

 给你一段长度为n的数组，给你一些数字1~x，要求你把这些数字插入数组中（可以插入在数组两端，也可以插入在数组里面），使得整个数组每两个相邻位置元素差值的绝对值的总和最小（其实就是把数组中的每一个元素当做一个对应高度的柱子，这个值就是从第一个柱子走到最后一个柱子的总步数，以下简称这个值为sum）请你找到一个插入方法，然后输出最小sum。

二.思路：

如果现有数组的元素范围是l~r那么，l~r的数都可以在数组中找到插入位置，并且不改变原数组的sum，（如果要插入x,只要有一个位置pos 此位置两侧元素一个小于x一个大于x即可，这样不会增加sum，因为这其实就是在两个位置之间铺了个台阶，并没有往上多走或者往下多走），那么1~l-1,和r+1~x 这些数字呢？其实我们可以把1~l-1这些数字看成1就行了，因为原数组中所有的元素肯定比1大，那么无论1放在哪里，都会有一个下坡路和上坡路要走，其实就是增加了步数（sum），而在这之间铺设“台阶”并不会增加sum，举个例子现在有两个数字2 3 我们把1 插入其中4 1 5 这时候21是下坡，1 3是上坡，本来从2到3 只需要走1步，现在多走了6步，而如果 把剩下的2 3 插入其中当做一个台阶，那么会变成 4 3 2 1 5 这样顺着台阶到1 并不会增加任何步数，或者4 1 2 3 5 顺着台阶到5也不会增加任何步数，因此只需要考虑1的位置即可，此时我们遍历每个放1的位置，然后计算会增加多少sum即可。r+1~x同理，整体思考看做x即可。

三.代码

#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]);//初始数组的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]));//这里算的是增加的最小值别忘了减去原有步数
        }
        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();
    }
}