新鲜出炉的Bloomberg电面！！！MARS组

亲 厉害了 不过还是没看懂第二题是啥意思 什么叫 “NY 或者SF 最多只能有一半的participants”？ 假如一共有奇数的人， 怎么分呢？

我觉得第二题最简单的做法就是另个帖子里有人提到的以每个人去两地的差值排序，先把一地的最大容量填满，然后剩下的全部去另个地方， 这样应该就是nlogn的time，constant space

wesker1988 发表于 2018-7-30 10:47
我觉得第二题最简单的做法就是另个帖子里有人提到的以每个人去两地的差值排序，先把一地的最大容量填满，然 ...

同意阿。和ｚｈａｏｃｏｎｇ２８的分析类似。但，其实算个差值，排个序就可以拉。比如一开始假设所有人去ＳＦ，然后挑出一般人去ＮＹ。每挑一个人对整体ｃｏｓｔ的影响是增加ｃｏｓｔＮＹ－ｃｏｓｔＳＦ。对ｃｏｓｔＮＹ－ｃｏｓｔＳＦ排序，找出最小的那些就是。

UCLA_andy 发表于 2018-7-18 23:51
怎么做？穷举嘛？然后backtrack？只需要求cost的值就好了。感觉像是dp。。

ｂａｃｋｔｒａｃｋ会超时吧，也没有合适的剪枝的条件。这样的话，ｂａｃｋｔｒａｃｋ起码就是Ｃｎ，　２ｎ的时间啦。