题解：P17746 「RSOI-1C」序列 / sequence

LongTen · 2026-11-11 13:17:00 · 题解

一个不用堆的做法

区间维护方式和铲雪一样，只是需要开一个新的数组 c_i 表示每次新开了多少区间，即有多少区间的起点在 i。在处理过期区间时只需要贪心地减去 c_{i-k} 这么多的区间即可。

不过需要注意的是在减去过期区间之前可能会有失效的区间（即区间数 cur 大于 b_i-a_i 的情况，这些区间的结尾不在我们现在的 i 处），这时我们记录一个 dec 表示提前结束的区间数量，每次处理过期区间时优先减去 dec，如果 dec 不足再减当前区间。

代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int n,k,a[N],b[N],c[N],ans=0;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        if(a[i]>b[i]) //判无解
        {
            cout<<-1;
            return 0;
        }
    }
    int cur=0,dec=0;
    for(int i=1;i<=n;i++)
    {
        if(i>k) //处理过期区间
        {
            if(dec>=c[i-k]) dec-=c[i-k];
            else 
            {
                cur-=c[i-k]-dec;
                dec=0;
            }
        }
        if(b[i]-a[i]>cur)
        {
            c[i]=b[i]-a[i]-cur; //记录区间起点数
            cur=b[i]-a[i];
            ans+=c[i];
        }
        else
        {
            dec+=cur-(b[i]-a[i]); //记录失效区间
            cur=b[i]-a[i];
        }
    }
    cout<<ans;
    return 0;
}