目录
题目链接：
https://www.acwing.com/problem/content/description/4911/
题目分析：
数据范围最大\(10^{14}\)，所以如果采用枚举一定会TLE，因为只有\(10^5\)天会运来新的草，所以我们可以只考虑运草的天。
假设当前到 \(d_2\) 天之前剩余干草的数量为cur，那么下一天就来到\(d_2\)，我们需结算至\(d_3\)天之前干草的数量。
因为当\(d_2\)来临时会立刻送来\(b_2\)捆草，所以用之前剩下的草的数量 + 送来的草的数量，有 \(cur + b2\)。
有多少天可以吃到草？从\(d_2\)天开始每天只会消耗掉一捆草，所以:
- 情况一： 该区间的天数 > 草的数量，该区间消耗的则是
草的数量。
情况二： 该区间的天数 < 草的数量，该区间消耗的则是天数。两种情况我们都只要最小值，有\(days = min(d_3-1-d_2 + 1，cur + b_2)\)。
以此类推，处理下一段区间的。
下一段区间的草的数量就是总草的数量 - 吃掉的数量即 \(cur + b_2 - days\)。
时间复杂度
因为处理区间时直接算出即可，所以是\(O(1)\)，一共有\(10^5\)区间所以总时间复杂度\(O(n)\)。
SF代码
#include <iostream>
const int MAXN = 100010;
int T, n, p, q, cnt;
int st[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> T >> n;
while (T -- ){
std::cin >> p >> q;
st[p] = q;
}
// cnt代表天数，只要存货n天即可
for (int i = 1; i <= n; ++ i)
if (st[i]) st[i] -- , st[i + 1] += st[i], cnt ++ ;
std::cout << cnt;
}
AC代码：
#include <iostream>
const int MXN = 100010;
#define int long long
int n, t, cur, ans;
struct seg
{
int id, w;
}segs[MXN];
int min(int a, int b)
{
return a < b ? a : b;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> t >> n;
for (int i = 1; i <= t; ++ i)
std::cin >> segs[i].id >> segs[i].w;
for (int i = 1; i < t; ++ i){
int d1 = segs[i].id, b1 = segs[i].w;
int d2 = segs[i + 1].id;
cur += b1; // 当前草的数量
int days = min(cur, d2 - d1);
cur = cur - days == 0 ? 0 : cur - days;
ans += days;
}
if (n >= segs[t].id){
int days = min(n - segs[t].id + 1, cur + segs[t].w);
ans += days;
}
std::cout << ans;
}