题意

输入描述

第一行是一个T≤20代表测试组数。
每组第一行是三个正整数n,m,p，分别代表城市数量、codeJan想要浏览的城市数量和codeJan当前的位置(单位为米)。
第二行包含n个正整数pos[i]表示第i个城市的位置，单位为米。
输入保证pos[i]<posi+1，并且p ≠ posi。
请在这里输入引用内容

输出描述

对于每组输入数据输出一个正整数表示 codeJan 至少需要走的距离。

思路

代码

//dfs
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int n,m,p;
ll pos[maxn];//城市的位置
int place;//存最大的小于初始位置的点
ll ans; //走过的距离
bool vis[maxn];//表示是否走过
void dfs(int x,int step,ll cnt){//step表示走过了几个城市 x表示当前位置 ，cnt表示当前走过的距离
    if(step == m){
        ans = min(cnt,ans);
        return ;
    }
    if(x+1 < n){//和右边的城市来回走
        ans = min(ans,cnt+(m-step)*(pos[x+1]-pos[x]));
    }
    if(x > 0){//和左边的城市来回走
        ans = min(ans,cnt+(m-step)*(pos[x]-pos[x-1]));
    }
    if(x+1 < n && vis[x+1]){//去右边城市
        vis[x+1] = false;
        dfs(x+1,step+1,cnt+pos[x+1]-pos[x]);
    }
    if(x >= 0&&vis[x-1]){//去左边城市
        vis[x-1] = false;
        dfs(x-1,step+1,cnt+pos[x]-pos[x-1]);
    }
}
int main(){
    int t = read();
    while(t--){
         n = read();m = read();p = read();
         place = -1;//初始位置
        for(int i = 0 ; i < n ;++i){
            pos[i] = read();
            if(pos[i]<p) place = i;
        }
        ans = 1e18+5;
        if(place >= 0){
            for(int i = 0 ; i < n ;++i) vis[i] = true;//清空状态
            vis[place] = false;
             dfs( place , 1 , p-pos[place] );
        }
        if(place+1 < n){
            for(int i = 0 ; i < n ;++i) vis[i] = true;
            vis[place+1] = false;
            dfs(place+1 , 1 ,pos[place+1] - p);
        }
        cout<<ans<<endl;
    }
}

//贪心
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+1;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
ll pos[N],n,m,p,x,t;
int main() {
    read(t);
    while(t--) {
        x=0;
        read(n),read(m),read(p);
        for(int i=1;i<=n;++i){
            read(pos[i]);
            if(p>pos[i]){
                x=i;
            }
        }
        ll ans=0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<n;++i){//i-i+1徘徊
            if(i<=x){
                if(x-i+1>m){//i~x
                    continue;
                }
                ll sx=m-(x-i+1),dis=p-pos[i];
                ans=min(ans,dis+sx*(pos[i+1]-pos[i]));
                if(sx&&x+1<=n){
                    ans=min(ans,(pos[x+1]-p)*2+dis+(sx-1)*(pos[i+1]-pos[i]));
                }//特判先p->x+1->p
            }else{
                if(i-x>m){//x+1~i
                    continue;
                }
                ll 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]));
                }//特判先p->x->p
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}