xenia-and-ringroad

Xenia and Ringroad

على طريق دائري \(n\) منزلًا مرقمة من \(1\) إلى \(n\) مع اتجاه عقارب الساعة. السير في اتجاه واحد فقط، مع اتجاه عقارب الساعة: من المنزل \(i\) إلى المنزل \(i + 1\)، ومن المنزل \(n\) إلى المنزل \(1\). الانتقال إلى المنزل التالي يستغرق وحدة زمن واحدة.

تبدأ كسينيا عند المنزل \(1\) ولديها \(m\) مهمة. لتنجز المهمة \(i\) يجب أن تكون عند المنزل \(a_i\)، ويجب أن تنجز المهام بالترتيب المعطى. أوجد أقل زمن لإنجاز كل المهام.

القيود:

\(2 \le n \le 10^5\)
\(1 \le m \le 10^5\)
\(1 \le a_i \le n\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(m\).
السطر الثاني: \(m\) عددًا صحيحًا \(a_1, a_2, \ldots, a_m\).

المخرجات:

عدد صحيح واحد — أقل زمن.

أمثلة:

الإدخال:

4 3
3 2 3

المخرجات:

(تتحرك كسينيا \(1 \to 2 \to 3\)، ثم \(3 \to 4 \to 1 \to 2\)، ثم \(2 \to 3\): \(2 + 3 + 1 = 6\) وحدات.)

الإدخال:

4 3
2 3 3

المخرجات:

الحل

نحاكي المشي. نحتفظ بالمنزل current الذي توجد فيه كسينيا الآن، ولكل مهمة نضيف زمن الوصول إلى المنزل \(a\):

إذا كان \(a \ge current\)، تمشي مع اتجاه عقارب الساعة دون أن تمر بالمنزل \(n\): \(a - current\) وحدة؛
إذا كان \(a < current\)، تمشي إلى المنزل \(n\)، ثم خطوة واحدة إلى المنزل \(1\)، ثم تتابع إلى المنزل \(a\): \(n - current + a\) وحدة.

ثم يصبح \(a\) هو current الجديد.

قد تستغرق كل مهمة ما يقارب \(n\) وحدة، لذلك قد يقارب الزمن الكلي \(10^5 \cdot 10^5 = 10^{10}\). هذا لا يتسع في int، لذلك نخزّنه في long long.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long time = 0;  // can be up to about 10^10
    int current = 1;

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;

        if (a >= current) {
            time += a - current;
        } else {
            time += n - current + a;  // go past house n and around to house a
        }
        current = a;
    }

    cout << time << "\n";
}