描述

假設你所在的公司有 個職位，編號從 到 ，編號越高對應的報酬越高，假設你是個新人，目前還在職位 ，每一天你都可以選擇在目前的職位上打工獲得對映報酬，或是花費一定量的錢接受下一個職位的培訓，培訓只需一天，第二天即可升職，但是不可以跨職位培訓。給出 個職位每天報酬 和 培訓費用 ， 表示從 到 的培訓費用?，F(xiàn)在你想通過工作買一臺價值 的計算機，求最少的工作天數(shù)。

分析

這一題是典型的貪心問題，是我的薄弱項，今天也是掙扎了10幾分鐘沒有好的思路就看題解了。說一下題解的思路，我們最終肯定是要依靠一個職位來攢錢，所以可以分為 種情況，而一旦確定了最終的職位，那么所需要攢的錢就是固定的（培訓費用加上計算機費用）。又因為職位報酬數(shù)組是遞增的，所以越早升職攢錢越快，前面的錢全部充當培訓費用一定是最優(yōu)的。分別計算 個職位下所需工作天數(shù)，選取其中最小的即可。

代碼

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    int t; cin >> t;
    int n, c;
    while(t--) {
        cin >> n >> c;
        int a[n], b[n-1];
        for(int& x: a) cin >> x;
        for(int& x: b) cin >> x;

        ll ans = (c+a[0]-1) / a[0]; // pos0
        ll cur = 0, bal = 0;
        for(int i = 1; i < n; i++) {  // pos1 ~ pos(n-1)
            ll workDays = b[i-1] > bal ? (b[i-1] - bal + a[i-1] - 1) / a[i-1] : 0ll;
            cur += (workDays + 1);  // 還有一天用于升職

            if(cur > ans) break;
            bal += (a[i-1] * workDays - b[i-1]);

            ll workDays2 = c > bal ? (c- bal + a[i] - 1) / a[i] : 0ll;
            ans = min(ans, cur+workDays2);
        }

        cout << ans << '\n';
    }
}