【每日一题】codeJan与旅行

问题：

给定n个城市坐标，每个城市可以多次到达，但是只有离开再回来才算次数+1，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。

解析：

通过观察法（观察大佬题解），发现这题是贪心，最优解一定是在 之间横跳或者直接一直朝前走到某个城市。具体方法：
1.判断能否直接走到i城市，如果走不到就抬走下一个，刚好是第m个到达的城市计算路径 (假设p为起点的位置，i在p的左端，x为p左端第一个元素, 表示第i个点的位置)就行了。如果走到第i个点还有次数多，那么就在 之间横跳就完事了。
2.为什么不是在之间横跳呢，很明显，两条边 如果 相等，和在一个点之间徘徊效果是一样的，如果不一样大，肯定是在小一点的边徘徊更好。
3.为什么不会跑到i前面再回到i横跳呢，如果会跑到i（假设 ）前面说明边 更短，那在这两个点之间徘徊肯定更优，没必要再回到i在 徘徊。
所以我们只需要枚举在i和i+1两个点间徘徊就行了，计算也很简单，答案取最小即可。但是这还不够。反例如下：
1
3 10 2
1 10 14
ans=42
明显是先走 再走到 10 然后在 之间徘徊。所以我们还要特判p先到p的另一端再回来徘徊的情况。
当然了只有可能去了另一端然后回来徘徊是最优解或者上述两种情况，不可能在另一端走一个以上的点再回来徘徊。

Code：

#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;
}