CF2272C Yet Another Black Cell Problem 题解

· · 题解

很显然这个东西具有单调性，考虑二分这个 k 然后 check 它是否合法。

首先对于黑点 a_i，如果 |a_i - a_{i-1}| \le k 或 |a_i - a_{i+1}| \le k，就可以直接借助 a_{i-1} 或 a_{i+1} 这种本来就是黑点的点将自己染黑。

否则，如果它左右的黑点都距离自己太远，只能新开一个黑点（题目里可以任选至多 x 个白点转变为黑点），要求该黑点位于 [a_i - k,a_i + k] 区间内。

得到一堆区间，我们计算出最少的黑点数，使得任何一个区间里都至少有一个黑点。

考虑怎么贪心做这个东西。很简单，因为区间长度固定，直接按照右端点（左端点也是一个意思）升序排序，然后扫一遍整个区间。如果上一个新黑点还包含在这个区间内，就直接借用一下，不开新的；否则，因为后续其他区间都比这个区间靠后，所以我们贪心选择该区间的右端点作为新黑点。统计个数并判断是否 \le x 即可。

CF tag 里有 dp，不知道哪里来的。

注意二分的范围为 [1,10^9]，一定不要把 0 包含进去！

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL INF = 1e9+1099;
struct node{LL l,r;}p[N];
LL T,n,cnt,a[N],l,r,Ans;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp(node d1,node d2){return d1.r<d2.r;}
bool check(LL k){
    int tot=0;
    for(int i=1;i<=n;i++){
        bool flag=1;
        if(i>1&&a[i]-a[i-1]<=k)flag=0;
        if(i<n&&a[i+1]-a[i]<=k)flag=0;
        if(flag)p[++tot]={a[i]-k,a[i]+k};
    }
    int hav=0;LL now=0;
    for(int i=1;i<=tot;i++)
        if(i==1||now<p[i].l)++hav,now=p[i].r;
    return (hav<=cnt);
}
int main(){
    T=read();
    while(T--){
        n=read(),cnt=read();
        for(int i=1;i<=n;i++)a[i]=read();
        l=1,r=INF,Ans=INF;
        while(l<=r){
            LL mid=(l+r)>>1;
            if(check(mid))Ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<Ans<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！