【JXOI 2017】加法 / 题解

Description

可怜有一个长度为 $n$ 的正整数序列 $A$，但是她觉得 $A$ 中的数字太小了，这让她很不开心。

于是她选择了 $m$ 个区间 $[l_i, r_i]$ 和两个正整数 $a, k$。她打算从这 $m$ 个区间里选出恰好 $k$ 个区间，并对每个区间执行一次区间加 $a$ 的操作。（每个区间最多只能选择一次。）

对区间 $[l, r]$ 进行一次加 $a$ 操作可以定义为对于所有 $i ∈ [l, r]$，将 $A_i$ 变成 $A_i + k$。现在可怜想要知道怎么选择区间才能让操作后的序列的最小值尽可能的大，即最大化 $\min A_i$。

Idea

直接二分答案，贪心判断。

判断的时候从左到右扫描序列上每个点。开两个优先队列，分别维护当前可以加入的区间，和已经加入的区间。然后只要不断给 $A_i$ 加上 $k$，直到满足当前二分的值，或者可用区间为 $0$。

Code

#include<bits/stdc++.h>
#define mid (L+R>>1)
#define N 200010
using namespace std;
int n,m,k,d,a[N];
vector<int> r[N];
priority_queue<int,vector<int>,greater<int> > H;
priority_queue<int> Q;
bool check(int x){
    while(!Q.empty()) Q.pop();
    while(!H.empty()) H.pop();
    int tk=k;
    for(int i=1;i<=n;i++){
        for(int j=0;j<r[i].size();j++)
            Q.push(r[i][j]);    
        while(!H.empty()&&H.top()<i) H.pop();
        for(int j=a[i]+H.size()*d;j<x;j+=d){
            if(Q.empty()||tk<=0||Q.top()<i) return 0;
            H.push(Q.top()),Q.pop(),tk--;
        }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--){
        cin>>n>>m>>k>>d;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1,x,y;i<=m;i++)
            cin>>x>>y,r[x].push_back(y);
        int L,R;
        for(L=0,R=1e9;L<R;)
            if(check(mid)) L=mid+1;
            else R=mid;
        printf("%d\n",L-1);
        for(int i=1;i<=n;i++)
            r[i].clear();
    }
    return 0;
}