[文章目录]
Description
有一排n棵树，第i棵树的高度是Di。MHY要从第一棵树到第n棵树去找他的妹子玩。如果MHY在第i棵树，那么他可以跳到第i+1,i+2,...,i+k棵树。如果MHY跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。为了有体力和妹子玩，MHY要最小化劳累值。2<=N<=1 000 000
发现有三个限定：时间戳k，上一步的代价f，d的大小关系。斜率优化。
因为d的作用至多为1，所以按照f为第一关键字，d为第二关键字定义优先级，放入队列中进行优化。对于时间可以在出队的时候判断。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define N 1001000
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n,m,k,d[N],q[N],f[N];
//性质，不管当前面对的di是怎样的，f小的不会比f大的差，f相等的显然要取d大的。
//具有单调性。
bool cmp(int x,int y)//返回x是否比y优
{
return f[x]!=f[y] ? f[x]<f[y] : d[x]>=d[y];
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;++i) d[i]=read();
m=read();
while(m--)
{
k=read();
int l=1,r=1; q[1]=1; f[1]=0;
for(i=2;i<=n;++i)
{
while(l<=r&&q[l]<i-k) ++l;
//队列中只保证优先级顺序有序，时间戳的限定可以在用的时候考虑
f[i]=f[q[l]]+(d[q[l]]<=d[i]);
while(l<=r&&cmp(i,q[r])) --r;
//由于每次放入的一定是时间戳最新的，所以可以保证删除队尾不影响时间的限定条件
q[++r]=i;
}
printf("%d\n",f[n]);
}
return 0;
}