求C题的贪心证明

C题为什么是排序后一大一小的匹配呀。按照直觉的话,

两个数相乘,不应该是越接近的乘起来越大,所以一大一小匹配中间的那几对就会偏大。

所以我想的匹配方式是第一个跟第 n / 2 + 1个匹配,就是最小的跟中间的,这样综合一下的匹配。虽然这样匹配很容易造出反例,但是不知道为什么直觉上这样匹配是错误的。而且奇数的时候,为什么是孤立出最后一个元素。这个有办法证明出来吗?

全部评论

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
运营3年修炼中接简历辅导:你的科研项目经历里,只写了你的动作,没有写你的思考和成果,不要只写使用什么进行了什么,这等于罗列你的任务,简历是为了突出你的优秀,你在什么样的任务背景下,克服了什么样的困难,针对性地做了哪些事情,最后达成了什么成果(用数据体现你的成果和效率)
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务