P7471 [NOI Online 2021 入门组] 切蛋糕题解

lzqy_ · 2021-03-27 20:16:23 · 题解

这一道题做法是分类讨论。

假设 a\leq b\leq c，那么就有以下结论：

● a,b 等于 0

很明显，一刀都不用切，全部给 c 就可以了，切零刀。

● 有且仅有 a 等于 0

\quad$ ● $b=c

$\quad$ ● $b≠c

● $a,b,c≠0$ 且 $a=b$ （$b=c$ 同理）可以切两刀，分成的四份中，取任意相同的两份给 $a,b$，剩下相同的两份给 $c$ 即可（按照 $a=0\&b≠c$ 的结论推出） ● $a,b,c≠0$ 且 $a+b=c

可以切两刀，分成的四份中，取两份不同的给 a,b，剩下不同的两份给 c 便可以满足 a+b=c；依然按照 a=0\&b≠c 的结论得到，上述情况可以成立。

● 否则

切三刀。根据 a=0\&b≠c 的结论容易扩展得，切三刀可以分成任意三份的比例。

容易证明，切两刀可以将蛋糕分成任意比例的两份。

对于这一段的证明如下：

设圆的面积为 S，切两刀得到如下：

由于这两道是随意切的，所以 k 可以取到 0<k<1 的所有值。因此，同样颜色的扇形面积之和也可以取到 0<S'<S 的所有值。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x=0;
    register char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
int t,a[3];
int main()
{
    t=read();
    while(t--)
    {
        a[0]=read(),a[1]=read(),a[2]=read();
        //读到数组里面利于排序
        sort(a,a+3);
        //以下是上文的分类讨论：
        if(a[0]==0&&a[1]==0)
        {
            printf("0\n");
            continue;
        }
        if(a[0]==0)
        {
            if(a[1]==a[2])
                printf("1\n");
            else
                printf("2\n");
            continue;
        }
        if(a[0]==a[1]||a[1]==a[2])
        {
            printf("2\n");
            continue;
        }
        if(a[0]+a[1]==a[2])
        {
            printf("2\n");
            continue;
        }
        printf("3\n");
    }
    return 0;
}