Problem: Link
Submission: Link $$$O(n)$$$, 92ms!
Part1: Hint
By looking at the $$$4$$$ test cases, we find that answers for $$$b[i] = 1$$$ are the same.
Part2: The greedy strategy (for each index $$$i$$$)
First, we define some macros for convenience:
The previous index of $$$x$$$: #define pr(x) ((x) == 1 ? n : (x) - 1) The next index of $$$x$$$: #define ne(x) ((x) == n ? 1 : (x) + 1) The next $$$1$$$ in the loop: rt(x). We will describe it later. For example, let $$$b$$$ be an $$$1$$$-indexed array $$$[2, 1, 2, 1]$$$, then $$$rt(2)==4$$$ and $$$rt(4)==2$$$. Note that $$$rt(i)==i$$$ could happen, for example, $$$b==[2, 1, 2]$$$, then $$$rt(2)==2$$$.
while(true){
(1) If you are at the destination, break.
(2) When you stay at an i where b[i]==2, just pay 2a[i] for a[i] gas that enables you to move from $$$i$$$ to ne(i).
(3) When you stay at an i where b[i]==1:
}
outer loop:
