课堂听课笔记：【DOGE】

#include<iostream>
#include<cstdio>
using namespace std;

int heap[10001];  //模拟 堆(完全二叉树)，根节点：heap[1] 
int heap_size;  //存储  堆 heap 的大小 

void put(int d){  //向堆 heap 中添加元素 d
/* put 函数  算法：
1. 在堆尾加入元素 d，并把堆尾的这个结点置为当前结点
2. 比较当前结点元素与它的父结点元素的大小。【假设 当前结点为 i，则 当前结点的父结点 为 i/2】
如果 当前结点<它的父结点，则 交换它们的元素，并把当前结点的父结点置为当前结点，转 步骤2
如果 当前结点>=它的父结点，则 转 步骤3
3. 结束(return ;)
*/
    int now, next;  //now：存储 当前结点； next：存储 当前结点的父结点
	
	//步骤 1
	heap[++heap_size] = d;  //向堆尾加入元素 d，堆的大小自增 1 
	now = heap_size;  //设置 当前结点 now 为堆尾结点
	
	//步骤 2
	while(now > 1){  //重复 比较当前结点元素与它的父结点元素的大小，直到 当前结点的父结点为根节点(heap[1])，即 当前结点/2==1 
		next = now/2;  //设置 当前结点的父结点 next 为 当前结点/2
		
		//当前结点>=它的父结点：put 函数 结束
		if(heap[now] >= heap[next]) break;  //退出循环 
		//当前结点<它的父结点：交换 当前结点(heap[now]) 与 它的父结点(heap[next]) 的元素 
		swap(heap[now], heap[next]);  //swap(a, b)：交换 a 与 b 的值，头文件：iostream 
		now = next;  //设置 当前结点 now 为 当前结点的父结点 next
	}

    return ;  //步骤 3
}

int get(){  //从堆 heap 中取出并删除 最小元素
/* get 函数  算法：
1. 取出 堆根结点元素
2. 把 堆尾的结点(heap[len]，暂且用 len 表示 heap_size) 转移到 根(heap[1])的位置，将根覆盖，堆的大小减 1 
3. 把根结点置为当前父结点 parent
4. 如果 parent 无孩子【parent > len/2，假设 当前结点为 i，则 当前结点的左孩子 为 i*2，右孩子 为 i*2+1】
【对于 parent > len/2 时，若 parent=len/2+1，则 parent 的左孩子=len+2，右孩子=len+3。len+3>len+2>len(堆的长度)，说明 parent 无孩子】，
则 转 步骤6；
否则【parent <= len/2】，把 parent 的两（或一，当且仅当 parent == len/2 时）个孩子中元素最小的孩子 置为当前父结点的子结点 son
5. 比较 当前父结点(parent) 与 它的子结点(son) 的元素大小。 
如果 当前父结点>当前父结点的子结点，则 交换它们的元素，把 当前父结点的子结点 指向 当前父结点，转 步骤4；
如果 当前父结点<=当前父结点的子结点，则 转 步骤6
6. 结束(return ;)
*/
	int now, next, res;  //now：存储 当前父结点； next：存储 当前父结点的子结点中元素最小的子结点； res：临时存储 根结点的元素
	
	//步骤 1
	res = heap[1];  //临时存储 堆 heap 根结点的元素
	
	//步骤 2
	heap[1] = heap[heap_size--];  //设置 堆根结点(heap[1]) 为 堆尾结点，堆的大小自减 1  
	
	//步骤 3
	now = 1;  //设置 当前父结点 now 为 根结点
	
	//步骤 4
	while(now*2 <= heap_size){  //重复 比较当前父结点元素与它的子结点元素的大小，直到 当前父结点的子结点为超出堆的大小(heap_size)，即 当前结点*2 > heap_size 
		next = now*2;  //先设置 当前父结点的子结点 next 为 当前父结点的左孩子(此时 next 不一定 存储的是元素最小的子结点，需要进行比较)
		
		//next < heap_size：判断 当前父结点是否有右孩子； heap[next+1]<heap[next]：判断 当前父结点的右孩子(假设存在右孩子)是否小于当前父结点的左孩子
		if(next<heap_size && heap[next+1]<heap[next]) next++;  //经过比较 设置 next 为 当前父结点中元素最小的子结点
		
		//步骤 5
		//当前父结点<=它的子结点中元素最小的子结点：get 函数 结束
		if(heap[now] <= heap[next]) break;  //退出循环 
		//当前父结点>当前父结点的子结点：则 交换 当前父结点(heap[now]) 与 它最小的子结点(heap[next]) 的元素
		swap(heap[now], heap[next]);  //swap(a, b)：交换 a 与 b 的值，头文件：iostream 
		now = next;  //设置 当前父结点 now 为 当前父结点的子结点中元素最小的子结点 next
	}
	
	//步骤 6
	return res;  //返回 取出的根结点的元素
}


int main(){
    int n;  //存储 果子的种类数目 
    scanf("%d", &n);  //输入  果子的种类数目 n 

    for(int i=0; i<n; i++){
    	int x;  //存储 第 i 种果子的数目
        scanf("%d", &x);  //输入  第 i 种果子的数目 x 

        put(x);  //向堆 heap 中添加元素 x 
    }
    
    int ans=0;  //存储 最小体力耗费值
	for(int i=0; i<n-1; i++){  //合并果子次数：n-1 
		int x=get(), y=get();  //从堆 heap 中依次取出并删除 最小元素 x, y(取出并删除 元素 x 后 y 为 此时的最小元素)
		ans += x + y;  //最小体力耗费值 增加 x+y
		put(x+y);  //向堆 heap 中添加元素 x+y(将已合并的果子重新加入堆中，进行下一轮合并处理)
	}
 
	printf("%d\n", ans);  //输出  最小体力耗费值 ans

    return 0;
}

如有BUG，敬请指正！👀️