喵哈~！各位代码小能手们，今天由我，小猫娘 Xenia，来给大家带来一道关于我自己的问题的题解哦，嘻嘻~ 别看我只是只小猫娘，解决起算法问题来也是很厉害的喵！(ฅ'ω'ฅ)

这道题是关于我在一个环形路上跑腿的故事，让我们一起来看看怎么才能最快地完成所有任务吧！

B. Xenia and Ringroad

---

题目大意喵

故事是酱紫的：在一个有 n 个房子的环形城市里，房子们从 1 到 n 顺时针编号。这个城市的交通也是单向的，只能顺时针走哦。

我呢，刚刚搬到 1 号房子，然后接到了 m 个任务。要完成第 i 个任务，我必须先到达 a_i 号房子，并且在这之前必须完成所有编号小于 i 的任务。

一开始我在 1 号房子，从一个房子走到相邻的下一个房子需要 1 个单位的时间。问题就是，完成这 m 个任务，总共最少需要多少时间呢？

举个栗子： 有 4 个房子，3 个任务，任务地点分别是 3, 2, 3。

1. 我从 1 号房子出发，要去 3 号房子。顺时针走：1 → 2 → 3。花费时间 3 - 1 = 2。现在我在 3 号房子。
2. 下一个任务在 2 号房子。因为是单向顺时针，我不能从 3 直接退回到 2。我必须继续往前走：3 → 4 → 1 → 2。花费时间 (4 - 3) + (2 - 1) + 1 = 4。现在我在 2 号房子。
3. 最后一个任务在 3 号房子。我从 2 号出发，顺时针走：2 → 3。花费时间 3 - 2 = 1。现在我在 3 号房子。

总时间就是 2 + 4 + 1 = 7... 啊咧？好像哪里算错了喵？让我们再仔细看看样例的解释... 1 → 2 → 3 (时间2) → 4 → 1 → 2 (时间3) → 3 (时间1)，总共是6。 哦哦！从 3 到 4 是 1 单位时间，从 4 到 1 是 1 单位时间，从 1 到 2 是 1 单位时间，所以第二步是 3 单位时间！总时间是 2 + 3 + 1 = 6。看来计算要小心一点才行呢！

解题方法喵

这道题其实是一个简单的模拟题，我们只需要一步一步地计算我每次移动需要花费的时间，然后把它们全部加起来就好啦~

我的初始位置在 current_pos = 1。总花费时间 total_time = 0。

然后，我们按顺序处理每一个任务 a_i。假设下一个任务的地点是 next_pos。 这时候，就需要分两种情况来讨论了喵：

1. next_pos >= current_pos 这种情况比较简单！因为下一个任务地点就在我当前位置的前方（或者就是当前位置），而路又是顺时针的，我直接顺着路走过去就好啦。 花费的时间就是 next_pos - current_pos。 比如我从 2 号房子要去 4 号房子，直接走 2 → 3 → 4，花费 4 - 2 = 2 个单位时间。

2. next_pos < current_pos 这种情况稍微麻烦一点点。下一个任务地点在我当前位置的“后方”。但是交通是单向的，我不能掉头往回走！所以我必须绕一圈才能到达。 具体的路径是：从 current_pos 一直走到 n 号房子，然后再从 n 号房子走到 1 号房子，最后从 1 号房子走到 next_pos。

   • 从 current_pos 到 n 的时间是 n - current_pos。
   • 从 n 到 1 的时间是 1。
   • 从 1 到 next_pos 的时间是 next_pos - 1。 所以总花费时间是 (n - current_pos) + 1 + (next_pos - 1)，化简一下就是 n - current_pos + next_pos。 比如在 n=4 的环路上，我从 3 号房子要去 2 号房子，就要走 3 → 4 → 1 → 2。花费的时间是 (4 - 3) + (2 - 1) + 1 = 1 + 1 + 1 = 3。用我们的公式算也是 4 - 3 + 2 = 3，完全正确喵！

每完成一个任务，我的 current_pos 就会更新为 next_pos。我们只需要循环 m 次，把每次移动的时间累加到 total_time 里，最后的结果就是答案啦！

一个重要的小提醒：n 和 m 最大可以是 10^5。在最坏的情况下，每次移动都可能需要接近 n 的时间，总时间可能会达到 m * n，也就是 10^10。这个数字会超出普通 int 类型的范围（大约是 2 * 10^9），所以我们的 total_time 变量一定要用 long long 类型来存储，不然就会溢出导致答案错误哦！

---

题解代码 (C++)

下面就是具体的实现代码啦，我已经加上了详细的注释，方便大家理解每一句都在做什么喵~

#include <iostream>

int main() {
    // 使用快速 I/O，让程序跑得更快一点喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // n 是房子的数量, m 是任务的数量
    int n;
    int m;
    std::cin >> n >> m;

    // total_time 用来累计总时间
    // 必须用 long long 来防止数据溢出！这是个小陷阱哦~
    long long total_time = 0;
    
    // current_pos 记录我当前所在的位置
    // 根据题目，我一开始在 1 号房子
    int current_pos = 1;

    // 循环处理 m 个任务
    for (int i = 0; i < m; ++i) {
        // next_pos 是下一个任务的地点
        int next_pos;
        std::cin >> next_pos;

        // 计算从 current_pos 到 next_pos 的时间
        if (next_pos >= current_pos) {
            // 情况1：下一个地点在前方或就是当前地点
            // 直接顺时针走过去，时间就是二者之差
            total_time += next_pos - current_pos;
        } else {
            // 情况2：下一个地点在后方
            // 需要绕一圈才能到，时间是 (n - current_pos) + next_pos
            total_time += n - current_pos + next_pos;
        }
        
        // 完成任务后，我的位置就更新到了新的地点
        current_pos = next_pos;
    }

    // 输出最终的总时间
    std::cout << total_time << '\n';

    return 0;
}

---

知识点介绍

这道题虽然简单，但也能学到一些有用的东西呢！

1. 模拟 (Simulation) 这道题的核心思想就是模拟。我们没有用什么高深的算法，而是完全按照题目描述的规则，一步一步地追踪我的位置变化和时间花费。很多问题都可以通过清晰地模拟过程来解决，这是编程竞赛中最基础也最重要的能力之一哦。

2. 环形问题的处理 环形路、环形数组等问题在算法题中很常见。这道题的处理方式（通过 if-else 判断是否“过界”）是解决这类问题的一种经典思路。它体现了模块化或者说周期性的思想。其实，if (a < b) then (a-b+n) 这种逻辑本质上和取模运算 (a - b + n) % n 是等价的，都是在处理循环边界。学会这种思维，以后遇到类似的环形问题就能轻松应对啦！

3. 数据范围与数据类型 (Integer Overflow) 这是新手最容易踩的坑之一！在动手写代码前，一定要估算一下结果的最大值可能会是多少。像这道题，n, m <= 10^5，total_time 的最大值可以达到 10^5 * 10^5 = 10^{10}，这远远超过了 32 位整型 (int) 的最大值（约 2*10^9）。如果不使用 64 位整型 (long long in C++), 就会得到一个错误的答案。所以，养成检查数据范围并选择合适数据类型的好习惯非常重要喵！

好啦，今天的题解就到这里啦！希望我的讲解对大家有帮助喵~ 如果还有什么问题，随时可以再来找我哦！我们下次再见！(>^ω^<)