微信小程序开发之小程序架构篇的图解与分析
565
2022-08-27
hdu 4334 Trouble(两个数组寻找目标和)
题目: 大意:给出5个数组A[], B[], C[], D[] , E[],他们的长度都是n,求解是否存在这样的情况,从每一个数组内拿出一个数字满足:a+b+c+d+e=0
分析: 一开始是这样想的:将其中两个数组合并起来,剩下三个数组遍历,得到3数之和,其相反数作为合并数组的二分查找目标值,估计时间8e6log(4e4)=7e7,应该可以过,果断超时,原来是忘记了有50个样例,再乘以50时间就是3.4e9。再进一步,我合并三个数组用同样的思路去做,时间问题完美解决了,但是新合并的数组长度达到了8e6,于是MLE了。貌似,LL数组达到6的数量级就危险了
当训练结束后,疲惫加感冒的我躺在床上无所事事,这道题不断在脑海中出现……然后我想起了排序和指针这套组合拳,很多时候这对组合确实能发挥巨大的威力。用于此题:设原来的5个数组在a[5][N]中,合并a[0],a[1]–>A[], a[2],a[3]–>B[] 接着把他们排序,a[4]中的元素作为目标值,在A和B中寻找两个数字,他们的和等于目标值即可。最关键的地方,查找:设两个指针p1, p2。
最开始p1指向第一个元素,p2指向最后一个元素,两者所选的元素的和如果大于目标值p2后退(左移),小于目标值p1前进(右移)。如果存在目标值,我们一定可以找到!
code:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~