題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🌈 AWC0104A Election of the Class President

Problem Statement

題目簡述

班上有 NN 位學生，第 ii 位學生得到 AiA_i 票。
如果最高票只由一位學生取得，輸出該學生的編號；如果有多位學生並列最高票，則無法決定班長，輸出 −1-1。

Constraints

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 所有輸入皆為整數

思路：一次遍歷

只需要知道兩件事：

  1. 目前看過的最高票數 mxmx，以及其對應的編號（即 ansans ）
  2. 這個最高票目前出現的次數 cntcnt

按照題意模擬即可。若最高票只出現一次，輸出其編號；否則輸出 -1。

注意

mxmx 初始值要設為比 AiA_i 的最小值還小的數，否則若所有票數都是 0，會誤判為有多位學生並列最高票。因為 Ai≥0A_i \ge 0，可以將其設為 −1-1。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(1)\mathcal{O}(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    mx = -1
    ans = cnt = 0
    for i, x in enumerate(A, 1):
        if x > mx:
            mx = x
            ans = i
            cnt = 1
        elif x == mx:
            cnt += 1
    print(ans if cnt == 1 else -1)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Rosuuri. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.