解题思路:
首先这一看就是数学题【应该让雾之湖的Cirno来做(这题明显就很⑨$^*$)】。
*:⑨就是baka的意思。
其次,题目要求你在这$n$个人中找到一种关系图使得剩下的人最多,输出剩下的人数。
题目所说的朋友个数是指在场的,走了的就要减去。
关系是相互的。
(题目翻译有点误导人,没说明白)
当然要先画图模拟找规律啦!
规律:
一个人:
一个人就不画图了,明摆着当扫到0个朋友的人离开时他就要走。
两个人:
同上,图可以脑补,因为只存在两种关系(要么两个人是朋友,要么不是)。
同样,没有人可以剩下。
三个人:
咯,你们要的图:
如图所设的关系:
当0个朋友的人要走时,没有人要走;
当1个朋友的人要走时,2
、3
要走;
当2个朋友的人要走时,没有人要走;(此时1
的朋友个数为0
,巧妙地绕过了扫描)
这样我们就剩下了1个人。
四个人:
如图所设的关系:
当0个朋友的人要走时,没有人要走;
当1个朋友的人要走时,没有人要走;
当2个朋友的人要走时,1
、3
要走;
当3个朋友的人要走时,没有人要走;(此时2
和4
的朋友个数为1
,巧妙地绕过了扫描)
这样我们就剩下了2个人。
n个人:
(4人以后的情况就不画了,占的版面太多)
根据上述方法继续推,不难发现剩下的人数总是$n-2$。
所以我们就有以下关系(设答案为$ans$):
$$ ans= \begin{cases} 0, & 0 \leq n < 2 \\ n-2, & n \geq 2 \end{cases} $$
所以我们就有如下代码:
1 |
|