Link

Question

给定正整数 \(n\) 和长度为 \(n\) 的序列 \(x_i,y_i\) 保证 \(x_i\) 单调递增，你需要构造 \(m\) 个去年 \([L_i,R_i]\) ，\(m\) 有你指定，使得每个 \(x_i\)恰好被 \(y_i\) 个区间包含

最大化 \(min({R_i-L_i})\)，并求其值

Solution

贪心的去做，一段区间需要尽可能的大，需要满足

从一个 \(x_i+1\) 开始
到一个 \(x_i-1\) 结束
先开始的先结束，后开始的后结束

有了这三点思想，我们就可以用队列来模拟这个过程

如果 \(y_i= y_{i-1}\) 我们不需要做，把上一段的延长过来就好了
如果 \(y_i>y_{i-1}\) 我们需要从 \(x_{i-1}+1\) 开始，补一些边
如果 \(y_i < y_{i-1}\) 那么我们需要断一些变，断边的顺序就是加边的顺序

我们不可能一条一条的加边，考虑到一部分边的起始点和终止点都是相同的，所以用二元组 \((pos,number)\) 维护就好了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5,INF=1e9;
struct node{
    int pos,number;
};
int N,X[maxn],Y[maxn],hed=1,til,ans=INF;
node q[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    N=read();
    for(int i=1;i<=N;i++) X[i]=read();
    for(int i=1;i<=N;i++) Y[i]=read();
    X[0]=-INF;
    for(int i=1;i<=N;i++){
        if(Y[i]==Y[i-1]) continue;
        if(Y[i]>Y[i-1]) q[++til]=(node){X[i-1]+1,Y[i]-Y[i-1]};
        else {
            int now=Y[i-1]-Y[i];
            while(hed<=til&&q[hed].number<=now){
                ans = min(ans,X[i]-q[hed].pos);
                now -= q[hed].number;
                hed++;
            }
            if(hed<=til&&q[hed].number>now&&now) {
                q[hed].number-=now;now=0;
                ans=min(ans,X[i]-q[hed].pos);
            }
        }
    }
    if(ans==INF)printf("-1\n");
    else printf("%d\n",ans-1);
    return 0;
}