一.闲话

qwq，太菜了有情况没考虑到，使用了出题人给的hack数据后才明白。

出题人给的hack数据:
1
3 10 2
1 10 14

ans=42

二.题解

这题中，我们不难证明，那么最后我们一定会在两个点直接徘徊或者直达某个点。

证明如下：

若不在两点间徘徊有最短距离，设我们走的点的序列为:

(对于)

那么走的距离就是:

那么，对于其中的最小的那个

我们如果一直在t-1和t两个点间徘徊直到走的点的个数等于m这个策略用的距离就是:


明显的这个距离是小于等于上面的距离的，与我们假设不符合，所以，我们最后一定是在两点间徘徊的（若k=t的话，就是直达某个点了）

所以，我们可以考虑枚举在哪两个点间徘徊，那么，我们只需要枚举在i和i+1两个点间徘徊就行了，计算也很简单，答案取最小即可

但是，我们提交上去后，wa了，为啥？

看hack数据。

我们发现，我们最佳是在10和14两点之间徘徊，但是，我们可以在一开始的时候，先从p走到1，再从1走到10，开始徘徊，这样，我们就可以少徘徊一次，而我们从p走到1再到p，只用了2步，而徘徊一次需要4步，所以，我们如果先到1再从1到p的话，可以少走2步！

其实，分析式子的话也可以发现策略的不足。

因为，我们的式子其实只保证了这部分的距离是最小的，然而，前面我们走的是否最小却不能保证。

所以，我们每次再尝试先从p走到附近的一个点，再走到我们枚举的徘徊点看看这种策略是否可以使得距离更小。

可能有人会问，如果我走到附近两个或多个点，再到p，是否可能距离更小？

答案是不会的，因为，如果你走到附近两个或多个点后距离比我们当前算的更小。（为了方便说明我们只弄两个点设为x,y）

那么当且仅当，我们从x到y的距离小于我们枚举的徘徊的两个点之间的距离（化下式子就可以得出，我懒得化了qwq）

于是乎，我们发现，当我们枚举在x和y两个点徘徊时，答案就比上面我们那个策略还优，所以，我们不需要枚举先走到附近两个及以上的点再跑到目标点徘徊。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1;
int pos[N];int n,m,p,x;
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        x=0;
        scanf("%lld%lld%lld",&n,&m,&p);
        for(int i=1;i<=n;++i){
            scanf("%lld",&pos[i]);
            if(p>pos[i]){
                x=i;
            }
        }
        int ans=1e17;
        for(int i=1;i<n;++i){//i-i+1徘徊
            if(i<=x){
                if(x-i+1>m){
                    continue;
                }
                int sy=m-(x-i+1),dis=p-pos[i];
                ans=min(ans,dis+sy*(pos[i+1]-pos[i]));
                if(sy&&x+1<=n){
                    ans=min(ans,(pos[x+1]-p)*2+dis+(sy-1)*(pos[i+1]-pos[i]));
                }
            }else{
                if(i-x>m){
                    continue;
                }
                int sy=m-(i-x),dis=pos[i]-p;
                ans=min(ans,dis+sy*(pos[i+1]-pos[i]));
                if(sy&&x>=1){
                    ans=min(ans,(p-pos[x])*2+dis+(sy-1)*(pos[i+1]-pos[i]));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

update:

感谢@ 求求大佬带带我emm大佬提出的修改建议！

我们可以这么考虑这道题：

我们第一步，必然是到达p左边或右边的那两个城市之一(除非m=0)，那么我们可以考虑枚举我们将这个两个城市中的哪一个城市作为起点，这样的话，如果我们要使得策略最优的话，一定是直达我们枚举的徘徊城市（或者直达某个城市）

为什么呢？因为我们的起点现在是一个城市了，那么，我们其实根据上面的式子(起点为)：

如果我们不是直达我们枚举的徘徊城市，而要使得答案小于直达这个策略的话。（不妨设枚举的城市在起点右边）

那么，必然有行走的策略是：

我们先从起点向左若干步，再回到起点，再从起点到枚举城市。

但是，又因为为我们式子中最小的那个值，所以，我们向左走的话，只会使得距离增加（用若干个大于的值替换，那么和必然增大），所以这么走必然不是最优的

于是证毕。

其它的就差不多了，代码的话，我们只需要把p分成它左边和右边的那两个点，然后走，就无需考虑后退一步之类的情况了