题目描述
小爱在 1 点位置，目的是通过 n 个位置，通过第 i 点位置时，需要花费 ci 元。
最开始，小爱没有钱。她可以打工，若她在第 j 个点，她每打工一天，就可以赚 aj 元。
请问小爱至少需要打工几天，才能通过 n 号点？她可以在同一个地点打任意多天工。
输入格式
- 单个整数：表示 n
- 第二行到第 n+1 行：每行两个整数表示 ai 与 ci
输出格式
- 单个整数：表示小爱最少需要打多少天工。
数据范围
- 30% 的数据，1≤n≤10
- 60% 的数据，1≤n≤5000
- 100% 的数据，1≤n≤300,000
- 1≤ai≤100,000
- 1≤ci≤100,000
样例数据
输入:
3
1 10
2 10
3 10
输出:
19
说明:
1号位置上打工10天，然后在2号位置打工5天，在3号位置打工4天
题解
本题关键点：贪心算法，代码如下。
#include <iostream>
using namespace std;
int main() {
long long n,t,mx,day,sum;
cin >> n;
long long a[n];
long long c[n];
for (int i = 1; i <= n; i++) {
cin >> a[i] >> c[i];
}
mx = 0, day = 0, sum = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx, a[i]);
if (sum < c[i]) {
t = (c[i] - sum + mx - 1) / mx;
day += t;
sum = sum + t * mx - c[i];
} else {
sum = sum - c[i];
}
}
cout << day << endl;
return 0;
}