传送门

题意描述

有n个城市在数轴上，当前的位置是，p不和任何的城市重合，你现在需要经过个城市，每过城市可以多次经过，求最小的总距离。

Tags

  • 贪心
  • 数学

分析

本题的巧妙之处在于，第一次看起来，有3种可行的方案：

  1. 从起点的 左/右 出发，一直到访问了个城市。
  2. 从如果到了 起点 或 终点 依旧不够个城市，则往回走。
  3. 从某一点 开始，循环的往 和 两点走。

如果按照以上的思路实现代码，会很繁琐，不容易实现。
然通过证明得到，来回走 个点 要比 来回走 个点，对答案的贡献更低，所以我们是需要考虑方案3的情况。也就是在 和 两点内来回的走动，所以只需要枚举: 从到点，然后 剩余城市数量 * 去最小。
但是这样只能过 的数据，那我们考虑hack数据：

1
3 10 2
1 10 14
// ans = 42

可以看到在这个数据中，的路径是2->1->10->14..循环。可以看出先从2退到1，然后在向右循环，所以我们需要考虑 向左/右 回退一步的情况。

参考代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int pos[maxn];
int n, m, p;

int main(void) {
    FAST_IO;

    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m >> p;
        int x = 0;
        for (int i = 1; i <= n; i++) {
            cin >> pos[i];
            if (pos[i] < p) {
                x = i;
            }
        }
        ll ans = INFL;
        for (int i = 1; i < n; i++) {
            if (i <= x) {
                ll need = m - (x - i + 1);
                if (need < 0) continue;
                ll dis = p - pos[i];
                ans = min(ans, dis + need * (pos[i + 1] - pos[i]));
                // 向右退一步，然后再往i 和 i + 1点 来回走
                if (x + 1 <= n && need != 0) { // 需要保证右边存在点
                    ll d = pos[x + 1] - p;
                    ans = min(ans, d * 2 + (need - 1) * (pos[i + 1] - pos[i]) + dis);
                }
            } else {
                ll need = m - (i - x);
                if (need < 0) continue;
                ll dis = pos[i] - p;
                ans = min(ans, dis + need * (pos[i + 1] - pos[i]));
                // 同上所述 向左回退一步 并且要保证左边有点
                if (need != 0 && x >= 1) {
                    ll d = p - pos[x];
                    ans = min(ans, d * 2 + (need - 1) * (pos[i + 1] - pos[i]) + dis);
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}