贪心问题

描述

假设你所在的公司有 个职位，编号从 到 ，编号越高对应的报酬越高，假设你是个新人，目前还在职位 ，每一天你都可以选择在目前的职位上打工获得对映报酬，或是花费一定量的钱接受下一个职位的培训，培训只需一天，第二天即可升职，但是不可以跨职位培训。给出 个职位每天报酬 和 培训费用 ， 表示从 到 的培训费用。现在你想通过工作买一台价值 的计算机，求最少的工作天数。

分析

这一题是典型的贪心问题，是我的薄弱项，今天也是挣扎了10几分钟没有好的思路就看题解了。说一下题解的思路，我们最终肯定是要依靠一个职位来攒钱，所以可以分为 种情况，而一旦确定了最终的职位，那么所需要攒的钱就是固定的（培训费用加上计算机费用）。又因为职位报酬数组是递增的，所以越早升职攒钱越快，前面的钱全部充当培训费用一定是最优的。分别计算 个职位下所需工作天数，选取其中最小的即可。

代码

#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';
    }
}