E. New Game Plus!

贪心

这一题个人感觉倒不是多难。
主要靠直觉。
首先,如果没有k这个条件的话,我们肯定是从大到小的取元素。
这一题最开始,我们也应该从大到小地取元素。
同时此刻的cur即元素值也在不断变化。
一旦cur变为负数的时候,我们break一下。
然后问题来了,我们对于接下来的每一步都必然是负数的元素,该如何使用这k次机会
使得减少的值最小?
若接下来还剩m个元素,那其实就是将m+1个元素分为k+1组,从小到大地取元素。
为什么是这样。
首先分组这个概念肯定没有问题。那么我们看分组会带给我们什么?
最后一个人的影响为0!!!既然如此,我们当然要把最小的放在每组后面。
也就是,前k+1个最小作为每组的最后面!!
那么为什么是k+1组而不是k组?因为其实,最末端也是一组。
又为什么是m+1个元素而不是m个元素呢?因为,我们把开始时此刻为负数的cur也当成一个元素了!!
当然可以不这样,但是会非常麻烦!!!!!这是一个技巧!

然后,我们如何分组呢?
这也是一个技巧,很容易我们全部push进vector,然后遍历索引
ans+=v[i]*(i/(k+1))这样就可以了。
真的是十分巧妙!!

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-25 17:51
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务