CF163D Large Refrigerator 题解

· · 题解

CF163D Large Refrigerator 题解

upd on 2024.11.3：增加了均值不等式的证明。

题目传送门

本蒟蒻首杀的黑题，名副其实的水黑（doge

upd on 2024.11.3：怎么降紫了。。。

题意

此题题目描述简洁无废话，题意见题目描述。

分析

没有好方法，那就暴力搜索吧。

我们可以先假设 a\le b\le c，这样就大大减少了枚举次数。

分别暴力搜索 a,b，然后根据 V 求出 c，再求出 S，比较最小值即可。

由于时间复杂度不好计算，所以提交一下试试。

发现超时，考虑剪枝。

优化

引理（均值不等式）：a+b\ge 2\sqrt{ab}。

证明放在最后。

\because abc=V \therefore bc=\displaystyle \frac{V}{a} \because S=2(ab+ac+bc) \therefore \displaystyle \frac{S}{2}&=ab+ac+bc\\ &=a(b+c)+\displaystyle \frac{V}{a} \end{aligned}

然后我们发现这玩意长得很像均值不等式。

$\begin{aligned} \therefore a(b+c)+\displaystyle \frac{V}{a}&\ge2a\sqrt{bc}+\displaystyle \frac{V}{a}\\ &\ge2a\sqrt{\displaystyle \frac{V}{a}}+\displaystyle \frac{V}{a} \end{aligned}

即 \displaystyle \frac{S}{2}\ge2a\sqrt{\displaystyle \frac{V}{a}}+\displaystyle \frac{V}{a}

于是当 \displaystyle \frac{S}{2}<2a\sqrt{\displaystyle \frac{V}{a}}+\displaystyle \frac{V}{a} 时剪枝。

AC代码

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
long long t,k,a[100000],p[100000],v,minn,ma,mb,mc; // 十年 OI 一场空，不开 long long 见祖宗 
void dfsb(long long i,long long s,long long sum) // 搜索 b 
{
    if(sum*sum>v/i)return; // 保证 a<=b<=c 
    if(s>k)
    {
        long long kk=v/i/sum; // a 和 b 已经搜索完，求出 c 
        if(kk*sum+sum*i+i*kk<minn)minn=kk*sum+sum*i+i*kk,ma=i,mb=sum,mc=kk; // 比较最小值 
        return;
    }
    if(a[s]>0)a[s]--,dfsb(i,s,sum*p[s]),a[s]++; // 由于 V 是以质因子的形式给出，于是就可以这样搜索 
    dfsb(i,s+1,sum);
}
void dfsa(long long s,long long sum) // 搜索 a 
{
    if(sum*sum*sum>v)return; // 保证 a<=b<=c 
    if(s>k) // a 搜索完，再搜索 b 
    {
        if(2*sum*sqrt(v/sum)+v/sum<minn)dfsb(sum,1,1); // 剪枝 
        return;
    }
    if(a[s]>0)a[s]--,dfsa(s,sum*p[s]),a[s]++; // 由于 V 是以质因子的形式给出，于是就可以这样搜索 
    dfsa(s+1,sum);
}
int main()
{
    scanf("%lld",&t); // t 组数据 
    while(t--)
    {
        scanf("%lld",&k),v=1; // 多测不清空，爆零两行泪 
        for(long long i=1;i<=k;i++)
        {
            scanf("%lld%lld",&p[i],&a[i]);
            for(long long j=1;j<=a[i];j++)v*=p[i];
        }
        minn=9e18,dfsa(1,1); // 多测不清空，爆零两行泪 
        printf("%lld %lld %lld %lld\n",minn*2,ma,mb,mc);
    }
    return 0;
}

注意事项：

  1. 十年 OI 一场空，不开 long long 见祖宗！
  2. 多测不清空，爆零两行泪。

关于 a+b\ge 2\sqrt{ab} 的证明

首先我们有 (\sqrt a-\sqrt b)^2\ge 0。

拆开来得到 a+b-2\sqrt{ab}\ge 0。

移项得 a+b\ge 2\sqrt{ab}。

证毕。

后记 1：版权所有@KobeBeanBryantCox，请勿抄袭代码。

后记 2：写代码的习惯一定要好，代码不要乱七八糟，优秀的码风是很醉人的~

还有，能不能不要脸地要个赞呀QwQ