sorting - 超级时间复杂度：学年开始了，如何更好地安排学生的坐姿

Question

为 60 名学生安排座位，以及如何安排座位，使每个人的整体满意度最高。

规则如下：

1. 每个学生写下 3 个同学的名字，表示最想要的同桌。

2. 每个同学的满意度计算公式：

   • 如果学生有同桌，并且同桌是他/她写的三个名字之一，满意度+1，否则+0。

   • 如果同学座位前面有同学，并且同学是他/她写的3个名字之一，满意度+0.6，否则+0。

   • 如果同学座位后面有同学，并且同学是他/她写的3个名字之一，满意度+0.6，否则+0。

3. 班级整体满意度=每位同学满意度之和。

4. 找到整体班级满意度最高的座位计划排。

难度：60名学生，根据排列组合的知识，总座位数：60！=8320987112741390144276341183223364380754172606361245952449277696409600000000000000

通过穷举枚举，计算复杂度太大。

有什么好的计算方法吗？

我觉得有这样一个工具对老师和学生来说都是很好的。

我真的希望能得到你的帮助。

标签： sortingmathdata-structures