# APCS實作題2021年9月第3題：幸運數字

> 日期：2024年7月12日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g277)

## 題目

### 問題描述

在 $n$ 個人之中，每個人被分配到一個號碼，記錄為 $a_1, a_2, \dots, a_n$，這些號碼彼此都不相同，我們要找出當中最幸運的一個。已知在 $[L, R]$ 區間之中，最幸運號碼定義為：
1. 當 $L = R$ 時，幸運號碼為 $a_L$
2. 當 $L < R$ 時，找出當中最小號碼的位置 $m$，並以最小號碼所在的位置將整個區間區分為左邊 $[L, m-1]$ 與右邊 $[m+1, R]$，計算兩個區間各自的總和，總和比較大的區間即為幸運號碼所在的區間；如果兩個區間的總和相等，則幸運號碼位在右邊的區間，若區間不包含任何數字，總和視為 $0$。重複以上步驟直到收斂至1. 時即可找到幸運號碼。

請找出這 $n$ 個人之中的幸運號碼。
<br />

### 輸入說明

第一行輸入一個正整數 $n~(1 \leq n \leq 3 \times 10^5$，接下來有 $n$ 個數字 $a_1, a_2, \dots, a_n ~(1 \leq a_1 \leq 10^7)$。

配分
- 50%：$1 \leq a_i \leq n$，所有數字都介於 $1 \sim n$。
- 50%：無其他限制
<br />

### 輸出格式

輸出這 $n$ 個數字中的幸運數字數值
<br />

### 範例輸入1

5
4 2 3 1 5

### 範例輸出1

4

### 範例輸入2

8
3 9 4 5 1 6 2 8

### 範例輸出2

9

<br />

## Python 程式碼

### 寫法1，遞迴

很直接的寫法，完全按照題目的條件寫程式碼，但會因為計算次數過多，從第18筆測資開始超時。

def solve(ns):  # 自訂函式
    d = len(ns)  # 取 ns 的長度 d
    if d == 1: return ns[0]  # 如果 d 等於 1，已找到答案，回傳 ns[0]
    idx = ns.index(min(ns))  # 找 ns 中最小值的索引值 idx
    if idx == 0: return solve(ns[1:])  # 如果 idx 等於 0，用 ns[1:] 代入 solve
    elif idx == d-1: return solve(ns[:-1])  # 如果 idx 等於 -1，用 ns[:-1] 代入 solve
    else:  # 其它狀況
        left = ns[:idx]  # idx 左側串列
        right = ns[idx+1:]  # idx 右側串列
        if sum(left) > sum(right): return solve(left)  # 如果 left 和較大，用 left 代入 solve
        else: return solve(right)  # 否則用 right 代入 solve

n = int(input())  # 讀取 n
arr = list(map(int, input().split()))  # 讀取串列 arr
print(solve(arr))  # arr 代入 solve 求解

<br /><br />

### 寫法2，修改陣列內容，還是會超時

很直接的寫法，完全按照題目的條件寫程式碼，但會因為計算次數過多，從第18筆測資開始超時。

n = int(input())  # 讀取 n
arr = list(map(int, input().split()))  # 讀取串列 arr

while len(arr) > 1:  # 串列長度大於1繼續執行
    d = len(arr)  # 串列長度
    idx = arr.index(min(arr))  # 找最小值的索引值 idx
    if idx == 0: arr = arr[1:]  # 如最小值在最左邊，由索引值 1 開始取新的串列
    elif idx == d-1: arr = arr[:-1]  # 如最小值在最右邊，由開頭取到倒數第2位
    else:  # 其它狀況
        left = arr[:idx]  # 左側串列
        right = arr[idx+1:]  # 右側串列
        if sum(left) > sum(right): arr = left.copy()  # 如果左側串列和較大，arr 改為 left 的內容
        else: arr = right.copy()  # 否則 arr 改為 right 的內容

print(arr[0])  # 最後只剩下一項就是答案

<br /><br />

### 寫法3，利用排序及前綴和

從吳邦一教授的解題影片〈[PyAp45 Python APCS 題解：幸運數字(AP202109_3), ZeroJudge g277](https://youtu.be/ADu5T02-PCY?si=6GAGISpukfxztC7z)〉中看到的寫法，費時最久約為 1.1 s，使用記憶體最多約為 90.1 MB，通過測試。

n = int(input())  # 讀取 n
arr = [0] + list(map(int, input().split()))  # 讀取串列 arr
psum = arr.copy()  # 前綴和
for i in range(1, n): psum[i] += psum[i-1]
maxIdx = [(a, i) for i, a in enumerate(arr)]  # 將 arr 的值與索引值組成數組再放進串列
maxIdx.sort(reverse=True)  # 依照值由大到小排序
maxIdx.pop()  # 移除最後一筆 (0, 0)
left, right = 1, n  # 左、右側索引值

while left < right:  # 結束時 left == right
    while True:  # 一直由 maxIdx 最後面取出的資料及索引值
        a, i = maxIdx.pop()
        if i >= left and i <= right: break  # 直到索引值在 [left, right] 之間為止
    lsum = psum[i-1] - psum[left-1]  # 左側加總
    rsum = psum[right] - psum[i]  # 右側加總
    if lsum > rsum: right = i-1  # 幸運數字在左側，重設 right
    else: left = i+1  # 幸運數字在右側，重設 left
         
print(arr[left])  # 印出答案

<br /><br/>

## C++ 程式碼

由 Python 程式碼寫法3修改而成，費時最久約為 82 ms，使用記憶體最多約為 9.5 MB，通過測試。**加總的部分可能會超過 int 的上限造成溢位，改用 long long 才不會出事。**

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n; cin >> n;  // 讀取 n
    vector<LL> arr (n+1, 0), psum (n+1, 0);  // 資料 arr，前綴和 psum，為了避免出界，最前面加上 0
    vector<pair<LL, LL>> maxIdx (n, pair<LL, LL> ());  // 排序用的陣列，資料為 (a, i)
    for(int i=1; i<=n; i++) {  // 執行 n 次
        cin >> arr[i];  // 讀取資料填入 arr[i]
        psum[i] += psum[i-1] + arr[i];  // 計算前綴和
        maxIdx[i-1] = make_pair(arr[i], i);  // (arr[i], i) 組成 pair 放入 maxIdx
    }
    sort(maxIdx.begin(), maxIdx.end(), greater<>());  // 依照 a 由大到小排序
    
    int left = 1, right = n;  // 左、右側索引值
    while(left < right) {  // 結束時 left == right
        int a, i;  // 暫存資料及索引值的變數
        while(true) {  // 一直由 maxIdx 最後面取出的資料及索引值
            a = maxIdx.back().first;
            i = maxIdx.back().second;
            maxIdx.pop_back();
            if (i >= left && i <= right) break;  // 直到索引值在 [left, right] 之間為止
        }
        LL lsum = psum[i-1] - psum[left-1];  // 左側加總
        LL rsum = psum[right] - psum[i];  // 右側加總
        if (lsum > rsum) right = i-1;  // 幸運數字在左側，重設 right
        else left = i+1;  // 幸運數字在右側，重設 left
    }
    cout << arr[left] << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`