Untitled conversation
- User
[SEERC2020] Neo-Robin Hood
题目描述
Bobo最近参观了一个奇特的传送系统,该系统包含n个房间,编号为0到n-1,每个房间都安装了一个传送设备。每个传送设备都带有一个类似钟面板的仪表盘,上面有一个指针,显示顺时针顺序的数字0到n-1。最初,第i个(0≤i≤n-1)房间的传送设备上的仪表盘指针指向数字a_i。
当 Bobo在房间t(0≤t≤n-1)时,他可以进行以下操作任意次:
传送。立即传送到房间(t + a_t) mod n。 顺时针移动指针。设置a_t ← a_t+1。
每个操作耗费一个单位时间。Bobo从房间0开始,他想要尽快到达某个房间x。他想知道需要多少时间。
输入格式
输入的第一行包含两个整数n(2≤n≤10^5)和x(1≤x≤n-1),分别表示房间的数量和 Bobo的目标房间。接下来一行包含n个整数a_0, a_1,..., a_{n-1}(0≤a_i≤n-1),其中a_i(0≤i≤n-1)表示第i个房间中指针指向的数字。
输出格式
输出一个整数,表示 Bobo 从房间 0 到房间 x 所需的最短时间。
样例 #1
样例输入 #1
4 3 0 1 2 3样例输出 #1
4样例 #2
样例输入 #2
4 3 0 0 0 0样例输出 #2
4样例 #3
样例输入 #3
4 3 2 2 2 2样例输出 #3
2 ``` c++代码和思路 - Assistant
To solve the problem of finding the shortest time for Bobo to reach room
xfrom room0, we can break down the problem by understanding the operations available and optimizing their usage.Problem Recap
- Teleport: From room
t, Bobo can teleport to(t + a_t) mod nin 1 unit of time. - Rotate: From room
t, Bobo can incrementa_tby1(i.e.,a_t ← (a_t + 1) mod n) in 1 unit of time.
Key Insight
The most straightforward approach is to directly set
a_0toxand teleport. This would involve:- Rotating the pointer in room
0until it points tox. The number of rotations needed is(x - a_0) mod n. - Teleporting directly to room
xfrom room0. This teleportation takes1unit of time.
The total time for this approach is: [ \text{Total Time} = (x - a_0) \mod n + 1 ]
Verification with Samples
-
Sample 1:
n = 4, x = 3 a = [0, 1, 2, 3]- Rotations needed:
(3 - 0) mod 4 = 3 - Teleport time:
1 - Total time:
3 + 1 = 4(matches the sample output)
- Rotations needed:
-
Sample 3:
n = 4, x = 3 a = [2, 2, 2, 2]- Rotations needed:
(3 - 2) mod 4 = 1 - Teleport time:
1 - Total time:
1 + 1 = 2(matches the sample output)
- Rotations needed:
Optimality Check
Exploring alternative paths (like making intermediate jumps and rotations) typically results in the same or higher total time compared to directly setting
a_0toxand teleporting. Thus, the direct approach is optimal.Implementation
Given the above reasoning, the minimal time required can be computed directly without the need for more complex algorithms like BFS or Dijkstra's.
Here is the C++ implementation based on this logic:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,x; cin >> n >> x; vector<int> a(n); for(auto &c:a) cin>>c; int rotations = (x - a[0]) % n; if(rotations <0) rotations +=n; cout << rotations +1; }Explanation of the Code
- Input Handling: Read the number of rooms
n, the target roomx, and the current pointersafor each room. - Calculate Rotations: Compute the number of rotations needed to set
a_0toxusing(x - a[0]) mod n. Adjust for negative values by addingn. - Total Time: Sum the rotations with
1(for the teleport operation) and output the result.
Conclusion
This approach efficiently computes the minimal time by leveraging a direct teleport after adjusting the pointer in room
0. It avoids unnecessary complexity, ensuring optimal performance even for large values ofn(up to (10^5)). - Teleport: From room