思路
维持一个区间,代表当前能吃到草的天数范围,right 代表区间右端点的后一个端点,代表挨饿的第一天
遍历d[i],每次拿到一个d[i]和b[i],检查d[i]是否在当前区间之内
如果在就扩充区间的右端点,right += b[i],同时res += b[i];
如果不在就重新开一个区间,区间的右端点设为d[i] + b[i],同时res+= b[i];
注意每次扩充右端点的时候要检查是否越界,即right > t
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
LL d[N], b[N];
int main(){
LL n, t;
cin >> n >> t;
for(int i = 1; i <= n; i ++){
cin >> d[i] >> b[i];
}
LL right = 1, res = 0;
for(int i = 1; i <= n; i ++){
if(d[i] < right){
if(right + b[i] > t){
res += t + 1 - right;
break;
}
res += b[i];
right += b[i];
}
else{
right = d[i] + b[i];
if(right > t){
res += t + 1 - d[i];
break;
}else{
res += b[i];
}
}
}
cout << res << endl;
return 0;
}