P1016 · OFFICIAL SOLUTION

P1016 无终奇语官方题解

Gioush OJ · P1016 无终奇语

无终奇语

【题意简述】

给定正整数序列 $h_i$ 。可以选择一个长度不超过 $k$ 的连续区间直接斩杀，再额外造成不超过 $c$ 的伤害；被攻击过的士兵必须构成一个连续区间。求可攻击区间的最大长度。

【部分分】

枚举攻击区间 $[l,r]$ 与技能区间，可以得到一个朴素做法。固定 $[l,r]$ 后，最优技能区间一定是其中长度不超过 $k$ 的最大子段和，所以问题转化为判断 $\sum_{i=l}^r h_i-\operatorname{MaxK}(l,r)\le c$ 。

【正解】

因为 $h_i$ 均为正数，最优技能区间可以视为长度恰好为 $k$ 的子段，边界不足时由窗口控制。枚举左端点，右端点单调右移；每加入一个新的右端点，只会新增一个长度为 $k$ 的候选子段。用单调队列维护当前区间内候选子段和的最大值，即可在 $\mathcal{O}(1)$ 时间判断当前右端点能否继续右移。

【复杂度】

左右端点与每个候选子段都只进出一次，时间复杂度为 $\mathcal{O}(n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。前缀和需要使用 long long。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 2000105using namespace std;6 7int n,k,Line[MAXN],Ans=0;8long long c,Pre[MAXN];9 10struct Queue {11    int Tail=0,Head=1,Num[MAXN<<1];12    void Push(int a){Num[++Tail]=a;}13    void PopF(){Head++;} void PopB(){Tail--;}14    int Front(){return Num[Head];} int Back(){return Num[Tail];}15    int Size(){return Tail-Head+1;}16}Q;17 18long long Calc(int x) {19    return Pre[x]-Pre[x-k];20}21 22int main() {23    freopen("fable.in","r",stdin);24    freopen("fable.out","w",stdout);25    scanf("%d%d%lld",&n,&k,&c);26    for (int i=1;i<=n;i++) {27        scanf("%d",&Line[i]); Pre[i]=Pre[i-1]+Line[i]*1ll;28    }29    int p=k;30    Q.Push(k);31    for (int i=1;i<=n-k+1;i++) {32        if (Q.Size()&&Q.Front()-k<i-1) Q.PopF();33        long long Max=0;34        if (p<n) { Max=Calc(p+1); if (Q.Size()) Max=max(Max,Calc(Q.Front())); }35        while (p<n&&Pre[p+1]-Pre[i-1]-Max<=c) {36            p++;37            while (Q.Size()&&Calc(Q.Back())<=Calc(p)) Q.PopB();38            Q.Push(p);39            if(p<n) Max=max(Calc(p+1),Calc(Q.Front()));40        }41        Ans=max(p-i+1,Ans);42    }43    printf("%d\n",Ans);44}