---
tags：APCS 分治法 區間最大值 遞迴
---
# 2021年9月APCS 3. 幸運數字
題目連結：https://zerojudge.tw/ShowProblem?problemid=g277
###### tags: `APCS` `分治法` `區間最大值` `遞迴`

---
題目說明與想法：
題目要求在一個陣列中不斷的：**找尋最小值=>求出左右區間和=>判斷符合條件的區間並進行下一次遞迴**，最後求出目標

## 須注意事項:
- 題目時限只有 0.5s，需要優化時間。最基本的如使用 ios::sync_with_stdio(false) 等輸入優化方式。
- 找尋最小值，如果使用 C++ 內建的 min_element()、find()、distance()等方式，會 TLE，應使用排序過的 deque<pair<int(value),int(index)> 的方式來找最小值
- 左右區間和，優使用前綴和 (prefix-sum) 來解決

- 前綴和的陣列要開到 long long int ，否則會溢位

- 其他像是 index 之類的問題也要注意

code (AC)：

#include <bits/stdc++.h>
using namespace std;

int lucky;
vector<int> table;
vector<long long int> pre_sum; // 記得要開 long long
deque<pair<int,int>> n_idx;

void find_min(int left,int right,int &indx){
    while(true){
        pair<int,int> ind=n_idx.front();
        if (ind.second>=left && ind.second<=right){
            indx=ind.second;
            n_idx.pop_front();
            break;
        }
        else n_idx.pop_front();
    }
}

void finds(int left,int right){ // left,right 階包含在區間中，換句話說，區間為 [left,right]
    if (right==left) {
        lucky=table[left];
        return;
    }

    int ind;
    find_min(left,right,ind);
    
    //cout<<"min_num:"<<min_num<<endl;
    
    long long int left_sum,right_sum;
    if (ind==left) left_sum=0;
    else left_sum=pre_sum[ind]-pre_sum[left];
    
    if (ind==right) right_sum=0;
    else right_sum =pre_sum[right+1]-pre_sum[ind+1];
    //cout<<"left_sum"<<left_sum<<endl;
    //cout<<"right_sum"<<right_sum<<endl;
    
    if (left_sum>right_sum) finds(left,ind-1);
    else if (left_sum<=right_sum) finds(ind+1,right);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    
    
    for (int i=0;i<n;i++){
        int k;
        cin>>k;
        table.push_back(k);
        n_idx.push_back({k,i});
    }
    sort(n_idx.begin(),n_idx.end());
    pre_sum.push_back(0);
    pre_sum.push_back(table[0]);
    for (int i=2;i<=table.size();i++){
        pre_sum.push_back(pre_sum[i-1]+table[i-1]);
        //cout<<pre_sum[i]<<" ";
    }
    //cout<<endl;

    finds(0,table.size()-1);
    cout<<lucky<<endl;
    return 0;
}

通過截圖：

NA(90%) Code：

#include <bits/stdc++.h>
using namespace std;

int lucky;
vector<int> table;
vector<long long int> pre_sum;
void finds(int left,int right){ // left,right 階包含在區間中，換句話說，區間為 [left,right]
    if (right==left) {
        lucky=table[left];
        return;
    }

    int min_num=*min_element(table.begin()+left,table.begin()+right+1);
    //cout<<"min_num:"<<min_num<<endl;
    auto it=find(table.begin(),table.end(),min_num);
    int ind=distance(table.begin(),it);
    long long int left_sum,right_sum;
    if (ind==left) left_sum=0;
    else left_sum=pre_sum[ind]-pre_sum[left];
    
    if (ind==right) right_sum=0;
    else right_sum =pre_sum[right+1]-pre_sum[ind+1];
    //cout<<"left_sum"<<left_sum<<endl;
    //cout<<"right_sum"<<right_sum<<endl;
    
    if (left_sum>right_sum) finds(left,ind-1);
    else if (left_sum<=right_sum) finds(ind+1,right);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    
    for (int i=0;i<n;i++){
        int k;
        cin>>k;
        table.push_back(k);
    }
    pre_sum.push_back(0);
    pre_sum.push_back(table[0]);
    for (int i=2;i<=table.size();i++){
        pre_sum.push_back(pre_sum[i-1]+table[i-1]);
        //cout<<pre_sum[i]<<" ";
    }
    //cout<<endl;
    
    finds(0,table.size()-1);
    cout<<lucky<<endl;
    return 0;
}

4/20 更新
在側資加強版的題目中，發現會 stack overflow，因此參考別人的文章重寫了一個

#include<iostream>
#include<vector> //vector 
#include<utility> //pair
#include<algorithm> //sort()
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define num first
#define index second
using namespace std;
int n;
vector<int>people;
vector<pair<int,int>>num_index;
int find_min(int L,int R){
    while(true){
        pair<int,int> i=num_index.back();
        if(i.index>=L && i.index<=R){
            int ret=i.index;
            num_index.pop_back();
            return ret;
        }
        else num_index.pop_back();
    }
}
int main(){
    fastio;
    cin>>n;
    int a;
    people.push_back(0);
    for(int i=0;i<n;i++){
        cin>>a;
        people.push_back(a);
        num_index.push_back({a,i+1});
    }
    sort(num_index.begin(),num_index.end(),greater<pair<int,int>>());
    vector<long long>prefix_sum(n+1);
    prefix_sum[0]=0;
    for(int i=1;i<=n;i++){
        prefix_sum[i]=prefix_sum[i-1]+people[i];
    }
    int L=1,R=n;
    while(L<R){
        int pivot=find_min(L,R);
        if(prefix_sum[pivot-1]-prefix_sum[L-1]>prefix_sum[R]-prefix_sum[pivot]){
            R=pivot-1;
        }else L=pivot+1;
    }
    cout<<people[R]<<"\n";
    return 0;
}