【算法笔记】贪心专题

?int main(){
? ? ?sort(a,a+n);
? ? ?for(int i=0;i<n;i++)
? ? ? ? ?ans+=abs(a[i]-a[n/2]);
? ? ?cout<<ans;
?}

P7014 均分图书

算一下平均数，然后从第一堆开始每次把一堆搞成平均数。

感觉这里有点bug，其实是有可能出现第二堆的书全都移到第一堆也不够用的情况的，但是暂时还没想到怎么解决，先这样吧...

?int main(){
? ? ?sum=c/n; //计算平均数 
? ? ?for(int i=0;i<n;i++)
? ?  {
? ? ? ? ?if(a[i]!=sum) //判断一下是否等于平均数，如果等于就直接下一次。 
? ? ? ?  {
? ? ? ? ? ? ?a[i+1]=a[i+1]+(a[i]-sum); //移动纸牌 
? ? ? ? ? ? ?a[i]=sum; //移动过后就变成了平均数 
? ? ? ? ? ? ?d++; //移动次数增加一次 
? ? ? ?  }
? ?  }
? ? ?return d;
?}

P7015 合并果?

哈夫曼树的具象版，那就用构造哈夫曼树的方法来合并吧。

本解法用到了优先队列，因为构造过程不是简单的消耗元素，还会产生新的节点，我们需要在新的节点加入备选元素后，元素列表仍能保持有序，此时选择优先队列来存储备选元素是最合适的。

?int main(){
? ? ?priority_queue<int, vector<int>, greater<int>> heap;
? ? ?//把元素全插入该优先队列
? ? ?int res = 0;
? ? ?while (heap.size() > 1){//还没用完
? ? ? ? ?int a = heap.top(); heap.pop();//取两个最小的
? ? ? ? ?int b = heap.top(); heap.pop();
? ? ? ? ?res += a + b;//加起来
? ? ? ? ?heap.push(a + b);//新节点塞回去
? ?  }
? ? ?return res;
?}