Codeforces 339B Xenia and Ringroad Xenia 與環狀道路

難易度 : 1300

英文原文如下

Xenia lives in a city that has n houses built along the main ringroad. The ringroad houses are numbered 1 through n in the clockwise order. The ringroad traffic is one way and also is clockwise.

Xenia has recently moved into the ringroad house number 1. As a result, she’s got m things to do. In order to complete the i-th task, she needs to be in the house number a_i and complete all tasks with numbers less than i. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.

中文翻譯

Xenia 住在一個有 n 間沿著環狀道路建立的城市。這些房子被順時針標記了從 1 到 n 號，整條道路是順時針的單行道。

Xenia 最近搬進了編號1的房子，因此她有 m 件事要做。為了完成第 i 個任務，她需要在編號為 a_i 的屋子裡並且先完成所有號碼小於 i 的任務(也就是要按照任務順序)。最開始，Xenia 是從編號1的屋子開始移動的，找出完成所有任務所需的最少時間，每移動到相鄰的一個屋子都需要一單位的時間。

輸入

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵). The second line contains m integers a₁, a₂, …, a_m (1 ≤ a_i ≤ n). Note that Xenia can have multiple consecutive tasks in one house.

第一行包含了兩個整數 n 跟 m  (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵)。 第二行包含了 m 個整數 a₁, a₂, …, a_m (1 ≤ a_i ≤ n)。

輸出

Print a single integer — the time Xenia needs to complete all tasks.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

印出一個整數 – Xenia 完成所有任務所需的時間。

範例

4間房子，3個任務。 所以移動會是 1 > 3 > 2 > 3

解題思路

在我們的解法中，用一個變數來簡單儲存目前的位置，應該就可以很輕鬆地算出來了~

C#解決方案

方案1

string[] first = Console.ReadLine().Split(' '); // split by space
int n = int.Parse(first[0]); // number of houses

long[] missions = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

long now = 1;
long res = 0;

foreach (var m in missions)
{
    res += m >= now ? m - now : n - now + m;
    now = m;
}

Console.WriteLine(res);

要是下個任務的屋子編號大於等於目前的，那就加上中間的差值就好

要是小於，那就代表要走過最大編號的屋子再繞回來計算

結論

這一題有點簡單，說實在的第一題可能還麻煩點…

這一題出自於比賽 – Dashboard – Codeforces Round 197 (Div. 2) – Codeforces

然後這裡看這一系列的其他題目

• Codeforces 339A Helpful Maths 有用的數學 – 翻譯與解答

🧡如果文章有幫上你的忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 339B – Codeforces

一些其他的Codeforces文章