codeJan与旅行

题意:注释解释很清晰(逃.....)
题解:参考当时Wannafly挑战赛7的题解
如果要达到最小的值,那么最佳情况就是走到某一个点,然后找这个点两边距离最近的点,然后两点之间左右横跳(手动滑稽.jpg)
比如 对于这个,肯定是在20和21之间横跳所求值最小,然后就是枚举每一位对于p和m进行操作
时间复杂度:

#include <bits/stdc++.h>
using namespace std;
int T,n,m,p,a[200001];
int main()
{
    for(scanf("%d",&T);T;T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        int pos=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]<p) pos=i;
        }
        long long ret=1000000000000000LL;
        for(int i=1;i<=n;i++)
        {
            long long ans=abs(p-a[i]);
            int step=max(pos-i+1,i-pos);
            long long luogan=min(a[i]-a[i-1],a[i+1]-a[i]);
            if(i==1) luogan=a[2]-a[1];
            if(i==n) luogan=a[n]-a[n-1];
            if(step<=m)
                ret=min(ret,ans+luogan*(m-step));
            if(step<m && pos!=0 && pos!=n)
            {
                if(a[i]>p)
                    ret=min(ret,ans+luogan*(m-step-1)+(p-a[pos])*2);
                else
                    ret=min(ret,ans+luogan*(m-step-1)+(a[pos+1]-p)*2);
            }
        }
        printf("%lld\n",ret);
    }
    return 0;
}