贪心
这一题个人感觉倒不是多难。
主要靠直觉。
首先,如果没有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))这样就可以了。
真的是十分巧妙!!