是个多叉huffman树，思想类比合并果子。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct node {

	LL w, h;

	node(){}

	node(LL w, LL h):w(w), h(h){}

	inline bool operator <(const node &o)const {

		return w == o.w ? h > o.h : w > o.w;

	}

};

priority_queue<node>q;

int n, k;

int main () {

	scanf("%d%d", &n, &k);

	LL x, ans = 0;

	for(int i = 1; i <= n; ++i) {

		scanf("%lld", &x);

		q.push(node(x, 1));

	}

	int cnt = ((k-1) - (n-1)%(k-1)) % (k-1);

	while(cnt--) q.push(node(0, 1));

	cnt = q.size();

	while(cnt > 1) {

		LL w = 0, h = 0;

		for(int i = 1; i <= k; ++i)

			w += q.top().w, h = max(h, q.top().h), q.pop();

		ans += w;

		q.push(node(w, h+1));

		cnt -= k-1;

	}

	printf("%lld\n%lld\n", ans, q.top().h-1);

}

巴特西

「NOI2015」荷马史诗（k叉huffman树/k叉合并果子）

CODE

最新文章

热门文章

巴特西

「NOI2015」荷马史诗 （k叉huffman树/k叉合并果子）

CODE

最新文章

热门文章

「NOI2015」荷马史诗（k叉huffman树/k叉合并果子）