Overview

Find the index of the piece of meat with the minimum grilling time \(A_i\). If there are multiple pieces with the same minimum time, output the smallest index.

Analysis

Since all pieces of meat are placed on the grill at the same time, the piece that finishes grilling first is the one with the minimum \(A_i\). There is no need to simulate the passage of time; we can simply inspect \(A_1, A_2, \ldots, A_N\) in order. This naive linear scan is sufficiently fast.

What we need to be careful of is how to handle cases where there are multiple minima. For example, in:

\(A = (5, 2, 4, 2)\)

the \(2\)-nd and \(4\)-th pieces finish grilling at the same time, so the answer is \(2\).

If we inspect the pieces in increasing order of their indices and update the answer only when we find a value strictly smaller than the current minimum, the smallest index among those sharing the same minimum value will be preserved.

Conversely, if we also update when the value is equal, we would overwrite it with a larger index that appears later, leading to a wrong answer.

Algorithm

We maintain the following \(2\) variables:

• best: the minimum grilling time among the pieces of meat examined so far
• ans: the smallest index among the pieces of meat that finish grilling in that time

The procedure is as follows:

1. Initialize both ans and best to -1.
2. Inspect the pieces of meat in order from the \(1\)-st to the \(N\)-th piece:
   • If the answer has not been set yet (i.e., ans == -1), set the current piece as the answer.
   • If the current time is strictly less than best, update best and ans.
   • Otherwise, do not update.
3. Output ans.

At each point, ans represents the piece of meat with the smallest index among those examined so far that finishes grilling first. Therefore, the value of ans after examining all pieces is the desired answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

In the provided code, all input is read at once and stored in data, resulting in a space complexity of \(O(N)\). The process of finding the minimum itself uses \(O(1)\) additional space.

Key Implementation Points

• The update condition should be a < best. If you use a <= best, it will be overwritten by a larger index when a piece of meat with the same grilling time appears.

• ans == -1 indicates that no piece of meat has been chosen yet. This condition ensures that the first piece of meat is always chosen initially.

• data[0] is the number of pieces of meat \(N\), and data[i] is the grilling time of the \(i\)-th piece. By using range(1, n + 1), the \(1\)-based index of the meat can be directly stored in ans.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    ans = -1
    best = -1
    for i in range(1, n + 1):
        a = int(data[i])
        if ans == -1 or a < best:
            best = a
            ans = i
    print(ans)

main()

---

This editorial was generated by gpt-6-astra-medium.