F - Education
题意
有一个人 为了存够 c 元 每一天有两种操作
可以选择在当前职位工作一天并拿到a[i] 元钱
如果当前存款多于 b[i] 可以升职到下一个职位（下一个职位的日工资更高）
a[i] 和b[i] 都是递增数组
问：至少要多少天才能存够 c 元
思路
因为a[i] 是递增的 所以如果要升职就要尽早升职
遍历a[i] 计算出当前工资下需要多少天 取最小值 存在minn 中
然后判断升职的情况 如果能升职就直接升职 否则计算在当前工资下需要多少天能够升职
每步操作更新day
代码
#include<bits/stdc++.h> #define int long long #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 200050; int n, c; int a[N], b[N]; void solve() { cin >> n >> c; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n - 1; ++i) cin >> b[i]; int minn = LLONG_MAX; int day = 0; int money = 0; for (int i = 1; i <= n; ++i) { minn = min(minn, day + ((c - money) + a[i] - 1) / a[i]); //若一直在当前位置 需要多少天 // 升职的情况 if (i == n)break; if (money >= b[i]) { //如果够升职 直接升职 money -= b[i]; day++; } else { int x = ((b[i] - money) + a[i] - 1) / a[i]; // 还要工作多少天才能升职 money = money + x * a[i] - b[i]; day += x; day++; //升职花费一天 } } cout << minn << endl; } signed main() { int t; cin >> t; while (t--) solve(); return 0; }
