一道OA模拟题，看了两个小时都没什么思路，求大神看看

今天做OA前本来想随便做个模拟测试，结果心态炸了

题目难点在于有一个m*n的二维数组，每一行取出至少n/2个数。 总共取出大于m*n/2个数，求他们最大和最小值的差值， 要使得差值最小。
个人想法是对每一行先排个序，然后对每行取n/2个连续数求最大/最小值。但这样时间复杂度就是n^m了，明显行不通。


有能解惑的加米

ND0406 发表于 2022-10-03 21:09:37
难点就是在left都一样大的情况下 到底滑动哪个窗口呢？

两次滑动窗口中，有多个相同的left都是任意移动一个即可

第一次找k的窗口，如果有2个left相同且最小的行，无论你移动哪一个，最小的left都不会变（因为你移动了一行，另一行还是之前的最小left）,所以cost就不可能减小（最小left不变，最大right可能增大）,只有2行都移动完之后cost才可能减小，先移动哪个后移动哪个都无所谓

后面找最大数量的滑动窗口同理，2个相等的最小left，移动其中一个，另一个最小left不会变，所以最小left+k也不会变，right就无法扩展，可选数量就不可能增大，只有相等的最小left都移动了才有可能有进展

每行排序，然后每行搞一个大小为n/2的滑动窗口（每行存一个left和一个right）然后最大的right-最小的left即为当前cost，然后找出left最小的那一行，向右滑动一格，再求一遍cost，所有行都滑到头以后就可以知道最小的cost即k，过程中需要注意left一样大以及某些行已经滑到头了这种corner case。得到k之后，每一行再次新建滑动窗口，找出最小的left，然后把每一行的right扩展到最小left+k的位置，得到当前的最大数量，然后继续右移一格最小的left，扩展所有right，记录数量，所有行都滑到头就能得到最大数量

感觉算出最小差，然后再算能这个组成最小差的组合放的数? 既小于这个组合里较大的和大于这个组合里较小的?

补充内容 (2022-10-04 10:11 +08:00):
既然每个都要选m/2个，找到所有行里排序后，m/2位置最大的，和m/2+1位置最小的? 就是那一对?

楼主好题。但是无法加米。

“抱歉，您不能对匿名帖评分“

yurikaka 发表于 2022-10-03 19:09:18
每行排序，然后每行搞一个大小为n/2的滑动窗口（每行存一个left和一个right）然后最大的right-最小的left即为当前cost，然后找出left最小的那一行，向右滑动一格，再求一遍cost，

难点就是在left都一样大的情况下 到底滑动哪个窗口呢？

yurikaka 发表于 2022-10-03 19:09:18
每行排序，然后每行搞一个大小为n/2的滑动窗口（每行存一个left和一个right）然后最大的right-最小的left即为当前cost，然后找出left最小的那一行，向右滑动一格，再求一遍cost，

学到了. 根据left来移动window真是巧妙

14417335 发表于 2022-10-03 20:38:27
楼主好题。但是无法加米。

“抱歉，您不能对匿名帖评分“

哈哈。我是来求解答的，不是来骗米的。

这题是不是可以贪心啊

感觉可以证明说 一定至少有一行或者两行一定只取m/2个元素， 然后这一行或者两行 贡献出最大最小值

确定了最大最小值这个题目就很简单了