题目描述
津津上高中了。她在自己的妈妈的魔鬼训练下,成为了一个神犇,每次参加一次OI比赛必拿Au虐全场。每次她拿到一个Au后就很高兴。假设津津不会因为其它事高兴,并且她的高兴会持续T天(包包含获奖当天。就算在高兴的时候再次拿到Au,他的高兴也只能维持包括这次拿奖之日起T天,而不是额外增加T天的高兴时间,除非之后再拿奖)。请你帮忙检查一下津津接下来的的日程安排,要参加N场比赛,看看接下来的几天,津津会累计开心多久?
输入输出格式
输入格式:第一行两个整数N和T。
接下来一行,N个单调递增整数t_i,表示她在第t_i天的时候拿了一个Au。
输出格式:一个整数表示,津津累计开心多久。
输入输出样例
输入样例#1: 复制3 5 1 2 10输出样例#1: 复制
11
说明
1<=N<=200000
1<=T,t_i<=10^9,t_i单调递增。
Solution:
流汗=_=!,一道普及的题目开始还没看懂题意(语文的重要性)。简单来说本题就是求有多少天津津会开心,而重复的当然只能算一次。因为已经保证数列单调递增,所以只需判断后一次离这一次之间相隔的天数是否超过t,如果超过了则不存在重叠天数所以直接ans累加t,如果超过了则ans累加差值,但是要注意最后一次出现拿奖是不存在重叠的天数(显然因为后面没有再拿奖了),所以要记得ans累加上t。输出ans,完美解决了。
代码:
1 #include<bits/stdc++.h> 2 using namespace std ; 3 int n,t,a[200005]; 4 int main() 5 { 6 scanf("%d%d",&n,&t); 7 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 8 int ans=0; 9 for(int i=2;i<=n;i++) 10 if(a[i]-a[i-1]>t)ans+=t; 11 else ans+=a[i]-a[i-1]; 12 printf("%d\n",ans+t); 13 return 0; 14 }