AT_abc444_f 题解

· · 题解

听别人说这是个紫？！

不会吧！不会吧？不会吧……

别吓我，我打完 E 一直在想它啊 /ll

早知道看 G 去了（

答案具有单调性，考虑二分。显然是二分答案，二分中位数 p。

check 函数怎么写？考虑对每个数字进行拆分，做 DP。针对拆分情况，我们存储两个维度，数值 num 和个数 dp_i。形式类似一个经过了离散化后的桶。

具体怎么转移呢？考虑拆分 a_x，最初让 cnt=1 并 num_1 = a_x,dp_1 = 1，然后枚举 i 范围从 1 到 cnt，对 num_i 进行拆分。

怎么拆？数值 num_i 可以拆成 f_1 = \lfloor \frac{num_i}{2} \rfloor 和 f_2 = \lceil \frac{num_i}{2} \rceil，分别考虑。就假设现在考虑的值是 f 吧，首先判断是否满足 f \ge p，如果 f < p 当然就不需要考虑了。否则，先看 num_{cnt} 是不是等于 f，如果不是就得先让 cnt \gets cnt+1 并 num_{cnt} = f,dp_{cnt}=0。此时就一定有 num_{cnt}=f 了，接下来就是转移，只需要 dp_{cnt} \gets dp_{cnt} + dp_i 了，因为当前考虑的数值 num_i 有 dp_i 个，所以拆出来的 f——不论是 f_1 还是 f_2——也都有 dp_i 个。

DP 过程就结束了，最后我们还需要取拆分后得到的最终结果存起来。拆分后的结果是哪几项 DP？由于一个数至多拆成两个不同的数，所以我们只需要考虑后两位——也就是 cnt 和 cnt-1——放进一个临时 vector 存起来，方便后续使用。

把所有数字都拆完之后，就获得了一个至多 2n 个元素的 vector 数组，将其按照 num 从小到大排序，选取前 \lceil \frac{n+m}{2} \rceil 个。当然，如果个数都不够，那么 check 肯定不通过，否则你还得判断在当前选取拆分数字的情况下的答案是否合法。不合法当然不行，合法的话，就直接返回通过啦！

于是 check 函数就写完了，整道题也结束了。总的来说也没那么难……吧？

#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
using namespace std;
const int N = 1e5+5;
LL T,n,m,a[N],sum,l,r,Ans;
LL len,num[N],dp[N];vector<pLL> vec;
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 check(LL p){
    LL fcnt=0,need=(n+m+1)/2;//初始化
    for(LL i=1;i<=n;i++)fcnt+=(a[i]>=p);//最初就满足条件的
    if(fcnt+m<need)return 0;//最优也达不成，直接返回
    vec.clear();//清空 vector
    for(LL i=1;i<=n;i++){
        if(a[i]<p)continue;
        //本身不行更不用想分裂
        len=0,num[++len]=a[i],dp[len]=1;
        //初始化，只把 a[i] 塞进去，分裂 a[i]
        for(LL j=1;j<=len;j++){//枚举所有能被拆分的
            LL f1=(num[j]+1)/2,f2=num[j]/2;
            //num[j] 被拆分成 f1 和 f2 两个数字
            if(f1!=num[len]&&f1>=p)num[++len]=f1;//存 f1
            if(f1>=p)dp[len]+=dp[j];//累加个数
            if(f2!=num[len]&&f2>=p)num[++len]=f2;//存 f2
            if(f2>=p)dp[len]+=dp[j];//累加个数
            if(f1>=p)dp[j]=0;//分完了，清零
        }for(LL j=len;j>=max(1ll,len-1);j--)//仅枚举后两项
            if(dp[j])vec.pb({num[j],dp[j]}),dp[j]=0;//有值就塞值并清零
    }LL ss=sum,ecnt=need;//初始化
    sort(vec.begin(),vec.end());//排序
    for(auto [x,y]:vec){
        LL add=min(ecnt,y);//不能减爆
        ss-=x*add,ecnt-=add;//减
        if(ecnt<=0)break;//足够了
    }return (ecnt==0&&ss>=need-1);//判断条件
}
int main(){
    T=read();
    while(T--){
        n=read(),m=read(),sum=0;
        for(LL i=1;i<=n;i++)
            a[i]=read(),sum+=a[i];
        l=1,r=2000000000,Ans=1;
        while(l<=r){
            LL mid=(l+r+1)/2;
            if(check(mid))Ans=mid,l=mid+1;
            else r=mid-1;
        }cout<<Ans<<"\n";
    }
    return 0;
}

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