摘要
Title: 4908. 饥饿的牛
Tag: 区间合并
Memory Limit: 64 MB
Time Limit: 1000 ms

4908. 饥饿的牛

题意

贝茜是一头饥饿的牛。
每天晚上，如果牛棚中还有干草的话，贝茜都会吃掉其中的一捆。
初始时，牛棚中没有干草。
为了让贝茜不被饿死，农夫约翰制定了 N个给贝茜送干草的计划。
其中第 i个计划是在第 di天的白天给贝茜送去 bi捆干草。
请你计算，贝茜在第 1∼T天中有多少天有干草吃。
思路

区间合并变种
每个区间左端点即d，右端点为d + b - 1
不同的是，这里ed（终点）不能取最大，而应该直接扩充，因为粮草是一直储存着的
举个例子，比如 n=2 t=10
- 1计划5天送4捆
- 2计划5天送4捆
- 正确答案应该是6
另外要注意，不能超出t这个范围

代码

'''
Author: NEFU AB-IN
Date: 2023-06-15 14:46:06
FilePath: \Acwing\4908\4908.py
LastEditTime: 2023-07-06 01:03:20
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor


class sa:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, a):
        return self.x < a.x


# Final
N = int(2e5 + 10)
M = 20
INF = int(2e9)

# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65  # A -> 0
NTL = lambda x: ascii_uppercase[x]  # 0 -> A
AR = lambda x: [x] * N

# —————————————————————Division line ——————————————————————
a = AR(0)

st, ed = -1, -1
res = 0
n, t = read()

for i in range(n):
    d, b = read()
    l, r = d, min(d + b - 1, t)
    if ed < l:
        if st != -1:
            res += ed - st + 1
        st, ed = l, r
    else:
        ed = min(t, ed + b)

if st != -1:
    res += min(ed, t) - st + 1

print(res)

4908. 饥饿的牛

题意

思路

代码