这道题的题意很简单,就是找两个数组中任意两个数之和的最小前n个数。
有意思的地方就在于他给我们的数据范围是1~100000
,对于两个数组的二重循环来说,是相当容易超时的,而且如果说我们用一个数组来存储两个数组的和,也就需要N^2大小的空间,这是我们所不能够接受的。
如果说我们用一个大根堆,用两重循环找和,当和小于根结点时,就能够用和替换掉根结点的数值,再向下调整,找新的最大值。当然由于给的数值都是从小到大的,如果一个和大于了根,那么他后面的所有的和就必然大于根,就可以break掉这层循环了
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/06/12/%E5%A0%86-%E4%B9%A0%E9%A2%98/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!