【每日一题】codeJan与旅行 题解

我哭了, 一大早起床本来想做个题后写作业, 结果被这道题搞了几个小时满脑子都是乱的还做不出来, 跑去看了题解

Solution

大致思想其实挺好想的(注意!是大致!) 因为题目保证不会存在 与城市节点重合的情况
我们先处理出 左右两个城市的位置(注意一下边界的处理)
然后很显然的, 我们可以找到从当前位置去到两个距离小的城市进行反复移动
令 为 到所枚举城市的距离, 为还需要访问多少个城市, 为到枚举点途径的城市数
有 , 最终结果就是 , 其中 为所枚举的终点城市
设移动到左边最近城市后枚举为方案1, 移动到右边最近城市后枚举为方案2
比较两个方案的 大小即可
这道题就做完了......吗?
其实没有!
因为会存在两种情况可能更优, 先往左走一个城市, 再往右边最近城市, 此时再做方案2
或者先往右走一个城市, 再往左边最近城市, 此时在做方案1
这里也是看了 聚聚的题解才知道
比如数据
1
3 10 2
1 10 14
答案是42
此时就会出现上面的情况

Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;
ll sum[N], a[N];

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n, m, p;
    cin >> n >> m >> p;
    int pos = 0;
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
      if(a[i] < p) pos = i;
    }
    ll ans = 1e18;
    for(int i = 1; i < n; i++) { 
      if(i <= pos) { // 往左走
        if(pos - i + 1 > m) continue;
        ll num = m - (pos - i + 1), dist = p - a[i];
        ans = min(ans, dist + num * (a[i + 1] - a[i]));
        if(num > 0 && pos + 1 <= n) { // 先往右走一格, 再往左走
          ans = min(ans, (a[pos + 1] - p) * 2 + dist + (num - 1) * (a[i + 1] - a[i])); 
        }
      } else { // 往右走
        if(i - pos > m) continue;
        ll num = m - (i - pos), dist = a[i] - p;
        ans = min(ans, dist + num * (a[i + 1] - a[i]));
        if(num > 0 && pos >= 1) { // 先左走一格 再往右走
          ans = min(ans, (p - a[pos]) * 2 + dist + (num - 1) * (a[i + 1] - a[i]));
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}