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

· · 题解

出题人题解。

由于我们只能执行加法操作，不妨先求出目标序列与初始序列的差值数组 d_i = b_i - a_i。

如果在任何位置出现了 d_i < 0，说明初始值已经超过了目标值，显然无法通过加法操作达到，直接输出 -1。

接下来考虑如何用最少的区间覆盖这些 d_i。

我们从左到右遍历 1 \sim n，并维护当前正在生效的区间数量（记为 \text{cur}）。当我们来到第 i 个位置时，首先要清除所有在 i - 1 处已经过期的区间。

然后比较当前的覆盖量 \text{cur} 与需求量 d_i：

因此，我们从优先队列中取出结束位置最小（最靠左）的区间，扣除多余的数量，直到 \text{cur} 降至 d_i。

由于 d_i \le 10^9，如果逐个处理区间会导致超时，我们需要将具有相同结束位置的区间合并处理。

可以使用 priority_queue 维护一个小根堆，里面存储「结束位置」和「区间数量」的 pair。这样每次取出结束位置最小的区间进行状态转移。

时间复杂度：遍历数组需要 O(n)，每个位置最多向优先队列中插入一次元素。堆的大小最大为 n，每次堆操作的复杂度为 O(\log n)。总时间复杂度为 O(n \log n)，足以通过 10^6 的数据。

空间复杂度 O(n)。

:::info[Code]

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename TP> inline TP read(TP &num)
{
    TP x=0;
    int f=0;
    char ch=getchar();
    while(ch<48||ch>57) f|=ch=='-',ch=getchar();
    while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
    (read(args),...);
}
template<typename TP> inline void write(TP x)
{
    (x<0)?(putchar('-'),x=-x):0;
    (x>9)?(write(x/10),0):0;
    putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
    write<TP>(x);
    puts("");
}
int n,k,a[1000005],b[1000005],d[1000005],cur,ans;
signed main()
{
    read(n,k);
    rep(i,1,n) read(a[i]);
    rep(i,1,n) read(b[i]),d[i]=b[i]-a[i];
    // 如果存在需要减去的值，无解输出 -1
    if(any_of(d+1,d+n+1,[](int x){return x<0;})) return puts("-1"),0;
    // 小根堆，存储 pair<区间结束位置,该结束位置的区间数量>
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
    rep(i,1,n)
    {
        // 弹出所有在当前位置 i 之前就已经失效的区间
        while(!q.empty()&&q.top().first<i) cur-=q.top().second,q.pop();
        // 如果当前覆盖的区间数量大于需要的数量，贪心地丢弃那些最先结束的区间
        if(cur>d[i])
        {
            int p=cur-d[i];
            while(p)
            {
                auto [dl,cnt]=q.top(); q.pop();
                int m=min(p,cnt); cur-=m,p-=m,cnt-=m;
                if(cnt>0) q.emplace(dl,cnt); // 如果没减完，重新加进队列
            }
        }
        // 如果当前覆盖的区间数量不足，贪心地新建一直延伸到 i+k-1 的区间
        if(cur<d[i])
        {
            q.emplace(i+k-1,d[i]-cur);
            ans+=d[i]-cur;
            cur=d[i];
        }
    }
    writeln(ans);
    return 0;
}

:::