
- 帖子
- 43
- 积分
- 84
- 技术
- 9
- 捐助
- 0
- 注册时间
- 2016-10-16
|
本帖最后由 hongrk 于 2019-5-1 18:16 编辑
答案应该是29(没有朋友是30,当然是最多,但这样似乎不太符合题目的意思……)。
不过我只是从逻辑上推出来的,还没有写出批处理。这道题我对直接写批没有什么想法,是打算推导出公式后直接让批处理算公式……
解:
这里把学生按顺序排为1 2 3 4……28 29 30,不妨设后者比前者学习更好。
则每个学生都各有2个朋友时,令每个学生的朋友为其前一位与后一位(如2则对于1、3,1则对于30、2)
如是,则根据题目要求,好学生有29个。只有学习最差的1不是好学生。
又因为30个学生不可能全为好学生(否则用来对比的那个学生是谁),所以29就是最大值。
对于普遍些的情况,设y为好学生总数,x为学生总数,n为一个学生有多少朋友。则好学生需要至少比m=floor[(n+1)/2]个朋友学习好。
n为偶数时,有y=x-m。如x=5,n=2时,可列出以下数列:123,234,345,451,512. 把每一项的中心当成一个学生,则其前后则为Ta的朋友。这样可以保证除了比其他人学习都好的那个人之外,其他好学生都恰恰比m个朋友学习好,实现最大化利用。此时显然只有成绩最差的m个学生不是好学生(此例中为1),故y=x-m=x-n/2
由此也可以直接推出1楼问题的结果,n=0时y最大,为30……
n为奇数就比较麻烦。
若x同时为奇数,则根本无法进行分组。即不能够实现题目要求的“每个学生都有相同数量的朋友”。
若x为偶数,则我还无从下手。使用@wankoilz的多边形法,能确定x≦6时都能分组,且最大结果都符合y=x-m。(除n=1外,则y=x/2)
但,x=8, n=3时,基本确定这个极限值是无法达到的;即只能做到y=x-m-1。我没有再向下。
在此抛砖引玉。 |
|