codeJan与旅行（贪心）

题目
题意：有n个城市排成一排，按递增给出城市坐标，codejan不在任意一个城市坐标上。
问：codejan访问m个城市最少需要走多少米，每个城市可以多次访问。
解法：
首先通过强大的观察法我们得到最终一定是在两个城市之间反复横跳，或者一次向一个方向走到m个城市，这两种方案。
具体如何得到的：

假设走到当前节点跳到后面节点后，还往后面走，那么就会到我们下一次选择下一个点位终点反复横跳。
如果这时候我们选择回头，那么一定是就回头一个格子，在这个地方反复横跳，为什么，如果在前一个格子距离更短，那我为什么不在再前面一个格子反复横跳，要多跑两个格子再后面这个地方反复横跳。
那么同理，如果我选择2个以上点反复横跳，花费一定会大于2个点反复横跳的花费，因为你选择了花费大的，让到达城市数目加1。

那么结合我上面分析的几种情况，得到最终一定是在两个连续的节点之间反复横跳，或者一次都不回头。
那么在这里又有两种情况，为什么给组样例就懂了。
3 4 2
1 10 12
ans = 42
没错这个地方我们出发点，选择回退一格，再重新前进反复横跳，为什么因为我们在回退一个格子再回来出发点，花费小于反复横跳一次的花费。
当然要选择最优的答案，那么这个地方就要特判出发点前面是不是有格子了，不能再我给的代码思路里面随便拿索引去找。注意判断边界。
给出代码，注意记录在我出发点之前的第一个城市位置，再枚举反复横跳的城市。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//int lcm(int a , int b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define cin(x) scanf("%lld" , &x);
#define endl '
'
const double esp = 1e-6;
const int N = 1e6+9;
const int maxn = 1e5+9;
int pos[maxn];


void solve(){
    int n , m , p ;
    int st = 0;
    scanf("%lld%lld%lld" , &n , &m , &p);
    rep(i , 1 , n){
        scanf("%lld" , &pos[i]);
        if(pos[i] < p) st = i ;//找到初始位置
    }
    int sum = 1e18;
    rep(i , 1 , n-1){
        if(i <= st){//目标在左边
            if(st - i + 1 > m) continue;//超过m次访问，不符
            int d = p - pos[i] , cnt = m-(st-i+1) ;
            sum = min(sum , d  + cnt * (pos[i+1]-pos[i]));//不会退
            if(cnt && st != n){
                sum = min(sum , d+(pos[st+1] - p)*2+(cnt-1)*(pos[i+1]-pos[i]));//回退
            }
        }else{
            if(i - (st+1)+1 > m) continue;
            int d = pos[i] - p  , cnt = m-(i-(st+1)+1);
            sum = min(sum , d  + (cnt)*(pos[i+1]-pos[i]));
            if(cnt && st!=0){
                sum = min(sum , d+2*(p-pos[st])+(cnt-1)*(pos[i+1]-pos[i]));
            }
        }
    }
    cout << sum << endl;
}

signed main()
{
    int _ ;cin>>_;while(_--)
    //while(~scanf("%lld%lld" , &n , &m) && n+m)
        solve();
}

codeJan与旅行 （贪心）

codeJan与旅行（贪心）