首先可以确定要分一个trouble,那一定是等分,这一点可以从公式化简得到。
所以难的问题是,给每一个trouble分几个人。当没有什么做法/头绪的时候,想一想贪心递推的操作(贪心是因为这个题数据量不应该是dp),大问题是否可以从小问题转化过来,每次多一个人的时候,这个人应该放到哪儿?可以试着遍历每一个trouble看看放在哪里会使得变小最多,但是这样是M^2的做法,但是这时候考虑“哪里小的最多”这个条件,以及,+1之后哪里变小的最多是完全取决于trouble的数值和他当前已经有的人的,所以可以用一个优先队列来存储“哪里变小的最多”这个信息!这样的话就是M^logM的算法了,可以通过本题。
自己当时为什么想挫了?主要是一开始想的把一个划分之后可以看成两个新的数,但是事实并非如此,新分出来的和原来的是不等价的,同一个trouble分出来的可以互相组合,但是不同德trouble之间不能组合,所以这种思路可以否定。所以其实每次都要考虑所有的trouble,取变小最多的那个,想到这里又觉得是M^2的算法,又没有继续,但是这时候思路已经是对的了,就可以考虑可以用什么优化,尤其是这种最值/顺序之类的问题,可以多考虑数据结构优化。