【每日一题】饥饿的牛

前言:

开始慢慢回归了!

题目:饥饿的牛

贝茜是一头饥饿的牛。

每天晚上，如果牛棚中还有干草的话，贝茜都会吃掉其中的一捆。

初始时，牛棚中没有干草。

为了让贝茜不被饿死，农夫约翰制定了 N� 个给贝茜送干草的计划。

其中第 i� 个计划是在第 di�� 天的白天给贝茜送去 bi�� 捆干草。

这些计划互不冲突，保证 1≤d1<d2<…<dN≤T1≤�1<�2<…<��≤�。

请你计算，贝茜在第 1∼T1∼� 天中有多少天有干草吃。

输入格式

第一行包含两个整数 N� 和 T�。

接下来 N� 行，每行包含两个整数 di,bi��,��。

输出格式

输出贝茜在第 1∼T1∼� 天中有干草吃的天数。

数据范围

1≤N≤1051≤�≤105,
1≤T≤10141≤�≤1014,
1≤di≤10141≤��≤1014,
1≤bi≤1091≤��≤109。

输入样例1：

1 5
1 2

输出样例1：

2

样例1解释

两捆干草在第 11 天早上被送到了牛棚，所以贝茜第 1,21,2 天有干草吃。

输入样例2：

2 5
1 2
5 10

输出样例2：

3

样例2解释

两捆干草在第 11 天早上被送到了牛棚，所以贝茜第 1,21,2 天有干草吃。

1010 捆干草在第 55 天早上被送到了牛棚，所以贝茜第 55 天有干草吃。

输入样例3：

2 5
1 10
5 10

输出样例3：

5

1010 捆干草在第 11 天早上被送到了牛棚，所以贝茜第 1∼51∼5 天都有干草吃。

代码;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static BufferedReader bReader =new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws NumberFormatException, IOException {
    	String s[]=bReader.readLine().split(" ");
    	int n=Integer.parseInt(s[0]);//计划数
    	long t=Long.parseLong(s[1]);//总共天数
    	long d[]=new long[100010];//存天数
    	long b[]=new long[100010];//对应天数的草量
    	long ans=0;//答案
    	long sum = 0;//剩下多少草
    	d[0]=0;
    	b[0]=0;

    	d[n]=t+1;
    	b[n]=0;
    	for(int i=0;i<n;i++) {
    	        s = bReader.readLine().split(" ");

               d[i] = Long.parseLong(s[0]);
               b[i] = Long.parseLong(s[1]);
    	}
    	for(int i=0;i<n;i++) {
    		sum+=b[i];
    		if(sum>=d[i+1]-d[i]) {
    			ans+=d[i+1]-d[i];
    			sum-=d[i+1]-d[i];
    		}else {
				ans+=sum;
				sum=0;
			}
    	}
    	System.out.println(ans);

}
}