h071 - 202109_3. 幸運數字（測資增強版）
題目描述
題目要求在給定一個包含 n 個數字的陣列中，找到「幸運數字」。幸運數字的定義是通過遞迴地將陣列分割成左右兩個子陣列，並比較兩個子陣列的總和，總和較大的子陣列包含幸運數字。這個過程一直重複，直到只剩下一個數字，這個數字就是幸運數字。
解題思路
本題的核心思想是使用分治法 (Divide and Conquer) 模擬題目描述中的幸運數字查找過程。為了提高效率，使用前綴和 (Prefix Sum) 來快速計算子陣列的總和。此外，使用 map 資料結構來儲存數字及其索引，以便快速找到最小數字的位置。
程式碼首先計算陣列的前綴和，並將數字及其索引儲存在 map 中。然後，使用一個 while 迴圈，不斷縮小搜尋範圍，直到 l 和 r 相等。在每次迴圈中，找到當前範圍內最小數字的索引，並計算左右子陣列的總和。根據總和的大小，更新 l 或 r，從而縮小搜尋範圍。最後，當 l 和 r 相等時，a[l] 就是幸運數字。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <map>
#include <set>
using namespace std;
long long l,r,n,a[300020],d[300020],it,rv,lv,tx;
map <long long,long long> mp;
map <long long,long long> :: iterator mit;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
r=n-1;
for(int i=0;i<n;++i){
cin >> a[i];
d[i+1]=d[i]+a[i];
mp[a[i]]=i;
}
mit=mp.begin();
while(l!=r){
while(mit->second>r||mit->second<l){
++mit;
}
it=mit->second;
rv=d[r+1]-d[it+1];
lv=d[it]-d[l];
if(rv<lv){
r=it-1;
}
else{
l=it+1;
}
}
cout << a[l];
}