rt,我觉得卡不到 O(n2)
代码:
#include<cstdio>
using namespace std;
int a[1000005];
int main()
{
//freopen("north.in","r",stdin);
//freopen("north.out","w",stdout);
int n,q;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&q);
for(int z=1;z<=q;z++){
int k,st=1,now=a[1],l=0;
scanf("%d",&k);
while(st<n){
if(st+k>=n){
if(now<=a[n])l++;
st=n;
}
else{
int min=2147483647,max=0,x,y,c=0,z;
for(int j=st+1;j<=st+k;j++){
if(a[j]>=max){
max=a[j];
x=j;
}
if(a[j]<=min){
min=a[j];
y=j;
}
if(a[j]>=c&&a[j]<now){
c=a[j];
z=j;
}
}
if(min>=now){
st=x;
now=max;
l++;
}
else{
st=z;
now=c;
}
}
}
printf("%d\n",l);
}
}