Codeforce 1539D-PriceFixed

題目連結: https://codeforces.com/problemset/problem/1539/D
題目大意:
一間商店裡，有$n$種商品，Lena 想買各$a_i$個，一次買一個，每個商品都是$2$元。
如果你在買第$i$種商品之前已經買了$b_i$個商品，那麼該商品只需花費$1$元。
請問: Lena最少需花多少錢才能買齊。

Sample

$Sample$ $Input$

3
3 4
1 3
1 5

$Sample$ $Output$

8

$Sample$ $Input$

5
2 7
2 8
1 2
2 4
1 8

$Sample$ $Output$

12

Solution

考慮兩種商品 $X,Y$，且有$b_X<b_Y$，如果我們想要買到優惠，顯然我們比較容易達到 $X$ 的量(即 $b_X$ )，所以我們可以將每種商品 $i$ 先依 $b_i$ 排序，接著利用雙指針，假設現在已經買了 $tot$ 個商品，而商品 $i$ 需要 $b_i-tot$ 個才能有優惠，那麼我們就從後面買 $b_i-tot$個商品，重複執行直到全部買完。

Code

#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>
#define fi first
#define se second
#define SpeedUP ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n;
pi a[100005];
// first 表 要買的個數(a) second 表 優惠需求的量(b)
void sol(){
    cin >>n;
    for (int i=0;i<n;i++) cin >>a[i].fi>>a[i].se;
    sort(a,a+n,[](pi lh,pi rh){
        return lh.se<rh.se; // 依照 b_i 排序
    });
    int r=n-1,tot=0,ans=0;
    for (int i=0;i<n;i++){
        if (i==r) break; // 當 i=r 時，直接跳出 之後處理
        if (tot>=a[i].se){
            ans+=a[i].fi;
            tot+=a[i].fi;
            a[i].fi=0;
        }
        else{
            while (r>i&&a[i].se-tot-a[r].fi>=0){
                tot+=a[r].fi;
                ans+=2*a[r].fi;
                r--;
            }
            if (i==r) break;
            int k=a[i].se-tot;
            ans+=2*k;
            a[r].fi-=k;
            tot+=k;
            ans+=a[i].fi;
            tot+=a[i].fi;
        }
    }
    // 處理 i==r 時
    if (tot>=a[r].se) {
        cout <<ans+a[r].fi;
    }
    else if (tot<a[r].se&&tot+a[r].fi>=a[r].se){
        cout <<ans+(a[r].se-tot)*2+(a[r].fi-(a[r].se-tot));
    }
    else{
        cout <<ans+a[r].fi*2;
    }

}
signed main(){
    SpeedUP 
    int tEst=1;
    //cin >>tEst;
    while (tEst--) sol();
   return 0;
}

時間複雜度: $O(nlogn+n)$，排序+計算。
這題想法不難，可是我實作太弱qwq，卡了很久才找到bug，AC code也很醜。