G家 面試題

上個月 G家 面試題
一時間只有naive的方法
不知是否有些思路

....个人感觉得把这个问题分成两步？注意到答案是和points的顺序有关的，我们除了要选出point，还得确保这些points的顺序能够最优化答案。朴素的做法需要枚举所有的可能的大小为K的子集，并枚举所有的顺序来计算答案，复杂度是O(C(N, K) K!)级别的。

我们可以证明（通过调整相邻的两个元素(x_i, y_i)和(x_{i+1}, y_{i+1})），如果对原先的points按照x/y降序进行排序，这个序一定能保证最优。所以我们可以这么做：先对所有的点按照x/y降序排序，那么我们只需要顺序取其中的某k个点就能保证最优性了。

接下来下一步就没什么想法了....目前做法的复杂度还是C(N, K)级别的，如果y坐标都是整数并且数据范围比较小的话应该可以使用类似背包问题的DP来做。但是题目里好像没有任何的说明....请问这个是phone interview的题还是onsite题呢？
调整法的证明如下：

假设我们已经有了一个解，其中某连续两个元素是(x_i, y_i)和(x_{i+1}, y_{i+1})，假设此时的答案是t.

如果我们交换了这两个相邻元素的顺序，答案会变成t+x_{i+1} * y_i - x_i * y_{i+1} => x_i / y_i < x_{i+1} / y_{i+1}。

lt0506 发表于 2019-11-8 12:29
这里面都是point啊

嗯，是的，我第一没理解题意。这题可以根据x,y 的值对点定义一个顺序。这个顺序是partial order，如果所有的点正好都有大小比较的话直接算就行，不行的话，就要在无法比较大小的那些点上做遍历。是一个DP和遍历混在一起的题。我感觉面试的时候能把思路说清楚就不得了了，目前水平自己是写不出来的。不知道有没有什么更好的解法。

整明白了, 这题你选不选k个都是一道难题.

第一次看见题目没理解到底在问什么.. 举的例子也极其特殊.

你这么不爱聊的人, 我也不多想讲思路了.

一句话总结就是找排序规则, 给出两个连续的元素时, 判断是否该交换即可.

原题是NOIP的, 改动了一下.

选出来的point在原数组里index是ordered的吗？如果是从0到n依次选k个，就有点dp的意思了   如果不是。。狗家真难

並不是ordered
因為如範例 {1, 9}, {5, 7}, {8, 3}
如果順序改變
Sum也會變
題目只要求Sum要最大
index並不一定要ordered

lzm34589 发表于 2019-10-29 08:19
並不是ordered
因為如範例 {1, 9}, {5, 7}, {8, 3}
如果順序改變

不一定要order？
那如果N = 2, K = 2,
X = {2,2}
Y=  {4,5}的话
答案就应该是10 而不是8？

是的
{2, 5} {2, 4}
2*0 + 2*5 = 10

对应每一个x_i 有一个对应的 x_i * sum_{i - 1}_{j = 1} y_j

选k个最大的即可。

如果无序的话，只能DFS穷举？应该是Akn的时间复杂度，如果有序的话，也许能DP吧，但是DP方程我也想不出来，如果有大佬能想出DP方程，求私

如果假设X跟Y的序列都是非负的，那么应该就是X要升序，Y要降序，就可以了吧。Greedy的思路。

clairefig 发表于 2019-10-30 22:36
如果假设X跟Y的序列都是非负的，那么应该就是X要升序，Y要降序，就可以了吧。Greedy的思路。

这里面都是point啊