【每日一题】codeJan与旅行

题意

给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。

solution

不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意边界情况。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;

LL ans, a[N];
int _, n, m, p;
void solve(int k, int res) {
  for (int i = k; i <= n; i++) {
    if (i > 1 && m - (i - k) >= 0) {
      LL tmp = res + (a[i] - a[k]) + (a[i] - a[i - 1]) * (m - (i - k));
      ans = min(ans, tmp);
    }
  }
  for (int i = k - 1; i >= 1; i--) {
    if (i < n && m - (k - i) >= 0) {
      LL tmp = res + (a[k] - a[i]) + (a[i + 1] - a[i]) * (m - (k - i));
      ans = min(ans, tmp);
    }
  }
}

int main() {
  for (scanf("%d", &_); _; _--) {
    ans = 1e18;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    m--;
    int k = upper_bound(a + 1, a + 1 + n, p) - a;
    if (k <= n) solve(k, a[k] - p);
    if (k > 1) solve(k - 1, p - a[k - 1]);
    printf("%lld\n", ans);
  }
  return 0;
}