题解 P5753 【[NOI2000]瓷片项链】

Roicer · 2020-10-18 17:33:42 · 题解

看到这道题还没有题解，就贡献一下本蒟蒻的第一篇题解吧。 （如果我思路没错的话）这题其实挺简单的···

首先

• 很容易想到要使总直径最大，则所有的泥巴都要用上
• 当泥巴总量大于单位用量（V>V0），则一定有解，反之输出0，结束

接下来针对有解的情况进行讨论（V>V0）

我们不妨设将泥巴分成k份，则V0=V/k，项链总长度设为s

则有： *s=kD=0.3k√(V/k-V0)** 。

为了方便比较，我们可以取个平方，设y=s²，整理后将等式看作一个关于k的二次函数：y=-0.09k²V0+0.09kV

可知在k=V/(2*V0)时s²取得最大值，即s取得最大值。而且此时我们将此时的k带入求单个陶片用料（V/k）得到单个用料为2V0，恒大于V0，（即一定有解），此时所得项链最长。

那么什么时候会有最优解不唯一的时候呢？——因为k是要为整数的，所以当k的最优取值不为整数时，我们要向最近整数点取整的，这是如果与k相邻的两个整数点离k一样远，那么最优解就有两个了，这时就要输出0了。

感觉有点啰嗦···将就着看吧╮(╯▽╰)╭

如果有什么问题，还请斧正 Thanks♪(･ω･)ﾉ

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
double v,c;

int main()
{
    cin>>v>>c;

    if(c>=v)
    {
        cout<<0;
        return 0;
    }
    double num=v/c;

    if(int(num)==num&&int(num)%2!=0)//最优解不唯一
    {
        cout<<0;
        return 0;
    }
    if(c==1)//因为所有整数都能被1整除，所以特判一下
    {
        cout<<v/(2*c);
        return 0;
    }
    cout<<int(v/(2*c)+0.5);
    return 0;
}

以上。 （点个赞鼓励一下吧）