标签：贪心，模拟
A new dogshow on TV is starting next week. On the show dogs are required to demonstratebottomless stomach, strategic thinking and self-preservation instinct. You andyour dog are invited to compete with other participants and naturally you wantto win!
On theshow a dog needs to eat as many bowls of dog food as possible (bottomlessstomach helps here). Dogs compete separately of each other and the rules are asfollows:
At thestart of the show the dog and the bowls are located on a line. The dog startsat position x = 0 and n bowls are located atpositions x = 1, x = 2, ..., x = n. Thebowls are numbered from 1 to n from left to right.After the show starts the dog immediately begins to run to the right to thefirst bowl.
The foodinside bowls is not ready for eating at the start because it is too hot (dog'sself-preservation instinct prevents eating). More formally, the dog can eatfrom the i-th bowl after ti seconds from thestart of the show or later.
It takesdog 1 second to move from the position x to theposition x + 1. The dogis not allowed to move to the left, the dog runs only to the right with theconstant speed 1 distance unit per second. When the dog reaches a bowl (say,the bowl i), the followingcases are possible:
· the food had cooled down (i.e. it passed atleast ti secondsfrom the show start): the dog immediately eats the food and runs to the rightwithout any stop,
· the food is hot (i.e. it passed less than ti seconds from the showstart): the dog has two options: to wait for the i-th bowl, eat the food and continue to run at the moment ti or to skip the i-th bowl and continue to run to theright without any stop.
After T seconds from thestart the show ends. If the dog reaches a bowl of food at moment T the dog can not eatit. The show stops before T seconds ifthe dog had run to the right of the last bowl.
You needto help your dog create a strategy with which the maximum possible number ofbowls of food will be eaten in T seconds.
Input
Twointeger numbers are given in the first line - n and T (1 ≤ n ≤ 200 000, 1 ≤ T ≤ 2·109) — thenumber of bowls of food and the time when the dog is stopped.
On thenext line numbers t1, t2, ..., tn (1 ≤ ti ≤ 109) aregiven, where ti is themoment of time when the i-th bowlof food is ready for eating.
Output
Output asingle integer — the maximum number of bowls of food the dog will be able toeat in T seconds.
Example
Input
3 5
1 5 3
Output
2
Input
1 2
1
Output
1
Input
1 1
1
Output
0
Note
In thefirst example the dog should skip the second bowl to eat from the two bowls(the first and the third).
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=200005;
int a[maxn],t[maxn];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
rep(i,0,n-1)scanf("%d",&t[i]);
int ans=0,cur=0;
for(int last=0;last<n&&last<m-1;last++){
if(t[last]<=m-1){
cur++;
int pos=last+(m-t[last]);
if(pos<n)a[pos]++;
}
cur-=a[last];
ans=max(ans,cur);
}
printf("%d\n",ans);
return 0;
}
