题解：P12168 [蓝桥杯 2024 省 C] 拼好数

minstdfx · 2025-04-12 23:51:21 · 题解

闲话

这出题人是不是吃拼好饭吃的脑积水了想出来的这题

题解

首先注意到只和每个数的数码 6 的个数有关。

然后注意到所有 6 的个数不小于 6 的数单成一组是不劣的。

接着注意到对 5 拿尽可能小的数去组二元组是不劣的，因为 5 只需要且总要和另一个数组。

接下来是 1234 的情况，发现因为 1 必然此时要和两个组，那么把 1 打包去和 4 按照 5 的贪心去做也同理不劣（边界条件 4+1+2 不优于 4+2）。

接下来对 123 的情况，由于最多要三元组所以不能 3+1+1+1，首先 3+2+1 不劣于 3+2+2，然后 3+2+1 不劣于 3+3（因为 1 没有 2,3 就废了）。

对于只有 23 的情况，有一个上界是 (3c_3+2c_2)/6，枚举两个 cnt 的余数发现是紧的。

否则 1 是没有用的。

然后就做完了。

a,b,c,d,e,f,g,d,_,*p;main(C){scanf("%*d");for(;~C;)(C=getchar())<48?(++*(&a+_),_=0):(_+=C==54&&_<6);for(p=&b;f>0;)_=1+(p==&f),(*p<_||(++g,--f,--*p)<_)&&++p;for(p=&b;e>0;)_=1+(p==&b||p==&e),(*p<_||(++g,p<&e&&--e,*p-=_)<_)&&++p;for(;b*d*c;--b,--d,--c)++g;printf("%d",g+(3*d+2*c)/6);}

什么，看不懂吗？

int main()
{
    cin>>n;
    for(int i=1,a;i<=n;++i)
        cin>>a,c[count6(a)]+=1;
    int ans=c[6];
    int ptr=1;
    while(c[5]>0)
    {
        int cc=(ptr==5)+1;
        if(cc>c[ptr] || (++ans,c[5]-=1,c[ptr]-=1)<cc) ++ptr;
    }
    while(c[4]>0 && c[1]>1)
    {
        --c[4]; --c[1]; --c[1];
        ++ans;
    }
    ptr=2;
    while(c[4]>0)
    {
        int cc=(ptr==4)+1;
        if(cc>c[ptr] || (++ans,c[4]-=1,c[ptr]-=1)<cc) ++ptr;
    }
    while(c[3] && c[2] && c[1])
    {
        --c[3]; --c[2]; --c[1];
        ans++;
    }
    ans+=(3*c[3]+2*c[2])/6;
}