题目
贝茜是一头饥饿的牛。
每天晚上,如果牛棚中还有干草的话,贝茜都会吃掉其中的一捆。
初始时,牛棚中没有干草。
为了让贝茜不被饿死,农夫约翰制定了 N 个给贝茜送干草的计划。
其中第 i 个计划是在第 di 天的白天给贝茜送去 bi 捆干草。
这些计划互不冲突,保证 1≤d1<d2<…<dN≤T。
请你计算,贝茜在第 1∼T 天中有多少天有干草吃。
输入格式
第一行包含两个整数 N 和 T。
接下来 N 行,每行包含两个整数 di,bi。
输出格式
输出贝茜在第 1∼T 天中有干草吃的天数。
数据范围
1≤N≤105,
1≤T≤1014,
1≤di≤1014,
1≤bi≤109
- 输入样例1:
1 5
1 2
- 输出样例1:
2
题解
import java.util.Scanner;/*** @author akuya* @create 2023-09-30-18:59*/
public class HungryCow {static long n,t;static long ans;static long top;//目前已经完成供梁的最后日期public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextLong();t=scanner.nextInt();long td=scanner.nextLong();top=td;long r=t-top+1;long tb=scanner.nextLong();if(tb>r){System.out.println(r);return;}else{ans+=tb;}for(long i=1;i<n;i++){td=scanner.nextLong();if(td>top){top=td;//大于最大供梁最大日期,则td成为最大日期}r=t-top+1;//计算剩余天书tb=scanner.nextLong();if(tb>r){ans+=r;System.out.println(ans);return;}else{ans+=tb;top=top+tb;}}System.out.println(ans);}
}
思路
这道题空间达到10的14次方,如果强行创建bool数组判断当天是否供梁又超时又爆空间。依照题意,给的数据天数递增,经过分析,创建变量"目前已经完成供梁的最后日期",若提供数据小于该变量则直接累加,大于该变量则将数据赋值于该变量。最后得到的结果即为正确答案。