广昌建设局官方网站,介绍个人网站的ppt怎么做,做网站手把手,一个人怎样做网站原题链接#xff1a;AcWing 4908.饥饿的牛 题目来源#xff1a;夏季每日一题2023
贝茜是一头饥饿的牛。
每天晚上#xff0c;如果牛棚中还有干草的话#xff0c;贝茜都会吃掉其中的一捆。
初始时#xff0c;牛棚中没有干草。
为了让贝茜不被饿死#xff0c;农夫约翰制…原题链接AcWing 4908.饥饿的牛 题目来源夏季每日一题2023
贝茜是一头饥饿的牛。
每天晚上如果牛棚中还有干草的话贝茜都会吃掉其中的一捆。
初始时牛棚中没有干草。
为了让贝茜不被饿死农夫约翰制定了 N 个给贝茜送干草的计划。
其中第 i 个计划是在第 di 天的白天给贝茜送去 bi 捆干草。
这些计划互不冲突保证 1≤d1d2…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样例1解释 两捆干草在第 1 天早上被送到了牛棚所以贝茜第 1,2 天有干草吃。
输入样例2
2 5
1 2
5 10输出样例2
3样例2解释 两捆干草在第 1 天早上被送到了牛棚所以贝茜第 1,2 天有干草吃。 10 捆干草在第 5 天早上被送到了牛棚所以贝茜第 5 天有干草吃。
输入样例3
2 5
1 10
5 10输出样例3
5
10捆干草在第 1 天早上被送到了牛棚所以贝茜第 1∼5 天都有干草吃。
方法一枚举
思路
首先看到1014 这种肯定要用long long而且看T的范围那么大枚举每一天显然是不可能考虑枚举每个区间对于一个区间来说能吃到草的有效天数为 min(区间长度干草数目) 因此枚举每个区间将每个区间的有效天数累加即可最后一段不要忘了
C 代码实现
#include iostream
#include algorithm
using namespace std;typedef long long ll;int n;
ll t;int main(){scanf(%d%lld, n, t);ll res 0, last 0, cur 0; // res结果 last上一区间右端点 cur当前干草数目for(int i 1; i n; i ){ll d, b;scanf(%lld%lld, d, b);ll len d - 1 - last; // [last1, d-1]区间的长度ll days min(cur, len); // 有效天数应该为区间长度和当前干草的最小值res days;// 更新cur和lastcur cur - days b;last d - 1;}res min(cur, t - last); // 扫尾printf(%lld\n, res);return 0;
}复杂度分析
时间复杂度O(n)循环次数和计划数n有关105级别O(n)绰绰有余空间复杂度O(1)常数个临时变量
