g277 - 3. 幸運數字
題目描述
題目要求在給定一個包含 n 個數字的陣列中，找到「幸運數字」。幸運數字的定義是通過遞迴地將陣列分割成左右兩個子陣列，並比較兩個子陣列的總和來確定。如果左邊的總和較小，則幸運數字在左邊的子陣列中，反之亦然。這個過程一直重複，直到只剩下一個數字，這個數字就是幸運數字。
解題思路
程式碼使用分治法來尋找幸運數字。首先，計算陣列的前綴和，並將每個數字及其索引儲存在 map 中，以便快速查找。然後，使用兩個指標 l 和 r 來表示當前區間。在每次迭代中，程式碼在 map 中找到索引在 [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];
}