### q838. 3. 貪心闖關
###### 2025年6月
### 題目大意
給定一個數列，每次從裡面選取最小值，如果有多個最小值，選擇所有最小值位置中最左邊的。如果在`t`以內，答案加上`t`後把這個值加到加下一個非`0`的位置，如果沒有下一個，則不必加到下一個位置。
### 解題想法
#### 1.priority_queue
每次都要找最小值位置$\Rightarrow$聯想到`priority_queue(heap)的特性`。
以`pair`作為容器，第一個放沙包數，第二個放位置。不過要先求最小，C++後面要加`greater<>`
#### 2. lazy update
不過每次下一個的值都會改變，不可能每次都從`pq(priority_queue)`刪去後再更新。這時可以使用`lazy update`的概念，也就是不直接刪除，而是新開一個陣列確認目前位置對到的值是否是有更新過的。
例如原本陣列`[1,4]`，`pq`是`{{1,0},{4,1}}`。更新完後變成`[0,5]`，這時原本`{4,1}`已經無效，但我們可以等pop出來再檢查，發現與現在不符就直接繼續。
#### 3. set&upper_bound
每次找下一個非`0`的位置，不可能使用迴圈檢查，因為時間複雜度$O(n)$。
可以開一個`set`儲存現在非`0`位置，每次使用`upper_bound`找尋下一個非`0`位置，如果是最後一個就不處理，最後在刪掉即可。時間複雜度$O(log n)$
### 複雜度
時間複雜度$O(n log n)$，不過常數偏大
空間複雜度$O(n)$
### 實作程式
:::spoiler C++ AC(0.7s, 28.8MB) code

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,t,x,ans=0;cin>>n>>t;
    vector<long long int> now_data(n,0);
    priority_queue<pair<long long int,int>,vector<pair<long long int,int>>,greater<>> pq;
    set<int> pos;
    for(int i=0;i<n;i++){
        cin>>x;
        pq.push({x,i});
        now_data[i]=x;
        pos.insert(i);
    }
    while (pos.size()>0 and pq.size()>0) {
        pair<long long int,int> data=pq.top();
        pq.pop();
        long long int now_cost=data.first;
        int now_index=data.second;
        if(now_cost>t)break;
        if(now_data[now_index]!=now_cost)continue;
        now_data[now_index]=0;
        auto it=(pos.upper_bound(now_index));
        if (it!=pos.end()){
            now_data[*it]+=now_cost;
            pq.push({now_data[*it],*it});
        }
        ans+=now_cost;
        pos.erase(now_index);
    }
    cout<<ans;
}

:::

::: spoiler C++ AC(0.4s,28.9MB) code(IO優化)

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long int n,t,x,ans=0;cin>>n>>t;
    vector<long long int> now_data(n,0);
    priority_queue<pair<long long int,int>,vector<pair<long long int,int>>,greater<>> pq;
    set<int> pos;
    for(int i=0;i<n;i++){
        cin>>x;
        pq.push({x,i});
        now_data[i]=x;
        pos.insert(i);
    }
    while (pos.size()>0 and pq.size()>0) {
        pair<long long int,int> data=pq.top();
        pq.pop();
        long long int now_cost=data.first;int now_index=data.second;
        if(now_cost>t)break;
        if(now_data[now_index]!=now_cost)continue;
        now_data[now_index]=0;
        auto it=(pos.upper_bound(now_index));
        if (it!=pos.end()){
            now_data[*it]+=now_cost;
            pq.push({now_data[*it],*it});
        }
        ans+=now_cost;
        pos.erase(now_index);
    }
    cout<<ans;
}

:::