对于相同权值,但不同高度的节点
在权值相同情况下,如果选择高度较高的节点建树
方法1 $\ \ \ \ $ 高度3
在权值相同情况下,如果选择高度较低的节点建树
方法二 $\ \ \ \ $ 高度2
因此在权值相同的情况下,要优先选择高度低的节点建树(即 方法二)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
const int N=100010;
int main()
{
int n,k;
cin>>n>>k;
priority_queue<PII,vector<PII>,greater<PII>> heap;
for(int i=0;i<n;i++)
{
ll x; cin>>x;
heap.push({x,0});
}
while((n-1)%(k-1)) n+=1,heap.push({0,0});//补0
ll ans=0;
while(heap.size()>1)
{
ll sum=0;
int d=0;
for(int i=0;i<k;i++)
{
auto t=heap.top();
heap.pop();
sum+=t.first;
d=max(d,t.second);
}
ans+=sum;
heap.push({sum,d+1});
}
cout<<ans<<'\n'<<heap.top().second;
return 0;
}