重要的技巧,从原点向右每秒一格,可以把a[i]-i看作新的距离
单调向右可以用优先队列/单调队列优化,此时pq维护的是以i为T秒结束后的人停留在的位置
做法能成立的原因是wait单调递减(时间上界不断减少,所以已经被删的不会再被加进队列里来,并且a[i]-i这个数组没有单调性,所以只能用优先队列,复杂度O(nlogn)
T秒本身到不算数,这在sol里被处理为循环到n+1,这是好理解的,如果T秒停在最后一个位置且最后一个位置被计数,那么等价于停在n+1位置,且该位置不计数
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5+10;
int n,T;
int a[N];
priority_queue<int> pq;
int ma;
int main()
{
cin>>n>>T;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n+1;i++){
int wait=T-i;
if(wait<0)break;
while(pq.size()&&pq.top()>wait)pq.pop();
ma=max(ma,(int)pq.size());
pq.push(a[i]-i);
}
cout<<ma<<endl;
}