力扣1046和1049学习笔记

1.概要

碎石头问题，拿两个石头碰撞，抵消共同质量的部分，1046是每次选最重两个，1049是任意选，让质量尽可能小。

2.大根堆

每次维护最重，如果直接排序的话复杂度过高，因此可以用大根堆，它会维护根是最大的

priority_queue<int>pq;

这就是大根堆，而插入和删除都是在堆顶是push和pop，top是取顶。

priority_queue<int,vector<int>,greater<int>>pq;

这是小根堆，因为大根堆是默认情况，所以可以不写后面两个参数。

3.1049

尽可能的让两堆石头质量相当，取m=sum/2作为背包的容量做背包问题。

状态转移方程是:

f[j]=max(f[j],f[j-v]+v);