codeJan与旅行(思维，枚举)

题目：

codeJan 非常喜欢旅行。现在有 n 个城市排在一条线上，并且 codeJan 的位置不和任何一个城市的位置重叠。
codeJan 想要游览 m 个城市，同时因为时间是不断变化的，游览一个城市多次也是允许的，但是不能永远待在一个城市，否则那样太无聊了。给出这些城市的位置，codeJan 想要知道游览 m 个城市至少需要走多少米？

做法：

这题数据太水了。写了发的A了。。不可思议。
由于城市可以多次旅行。所以不难想到找2个相邻的城市疯狂摇摆即可。 的思路是，先从起点p出发找一个落脚点x。然后从x出发枚举走到相邻的2座城市摇摆。
然而其实落脚点x是不需要枚举的，只需考虑距离起点p最近的2个城市即可。然后就变成的了。

代码：

:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int n, m, s, p[N];
ll solve(int id, int rest, ll pre){
    ll ans = 1e18;
    for (int i = 1; i <= n; ++i){
        int visted = abs(i-id);
        ll travel = abs(p[i]-p[id]);
        if (visted > rest) continue;
        if (i > 1){
            ans = min(ans, travel+1ll*(rest-visted)*(p[i]-p[i-1]));
        }
        if (i < n){
            ans = min(ans, travel+1ll*(rest-visted)*(p[i+1]-p[i]));
        }
    }
    return ans+pre;
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> m >> s;
        for (int i = 1; i <= n; ++i) cin >> p[i];
        int id = lower_bound(p+1, p+n+1, s) - p;
        ll ans = 1e18;
        for (int i = 1; i <= n; ++i){
            int done = (i < id) ? id-i : i-id+1;
            ll pre = abs(p[i]-s);
            ans = min(ans, solve(i, m-done, pre));
        }
        cout << ans << endl;
    }   
    return 0;
}

:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int n, m, s, p[N];
ll solve(int id, int rest, ll pre){
    ll ans = 1e18;
    for (int i = 1; i <= n; ++i){
        int visted = abs(i-id);
        ll travel = abs(p[i]-p[id]);
        if (visted > rest) continue;
        if (i > 1){
            ans = min(ans, travel+1ll*(rest-visted)*(p[i]-p[i-1]));
        }
        if (i < n){
            ans = min(ans, travel+1ll*(rest-visted)*(p[i+1]-p[i]));
        }
    }
    return ans+pre;
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> m >> s;
        for (int i = 1; i <= n; ++i) cin >> p[i];
        int id = lower_bound(p+1, p+n+1, s) - p;
        ll ans = 1e18;
        for (int i = id; i >= max(id-1, 1); --i){//拿上面代码，这里稍微改改即可
            int done = (i < id) ? id-i : i-id+1;
            ll pre = abs(p[i]-s);
            ans = min(ans, solve(i, m-done, pre));
        }
        cout << ans << endl;
    }   
    return 0;
}