为shopify做推广的网站,电商网站功能设计,苏州市建设工程交易网,郑州仿站模板网站建设解决这个问题前可以先把这三个问题想清楚 1、为什么可以使用哈夫曼树进行求解#xff1f; 考虑逆操作 参考题解链接 2、为什么恰好是按照每堆所需要的数量分#xff1f;针对某一堆#xff0c;可以先分一部分吗#xff1f; 首先这里按照每堆所正好含有的数量进行划分#x…解决这个问题前可以先把这三个问题想清楚 1、为什么可以使用哈夫曼树进行求解 考虑逆操作 参考题解链接 2、为什么恰好是按照每堆所需要的数量分针对某一堆可以先分一部分吗 首先这里按照每堆所正好含有的数量进行划分是最优的 因为假想我们对于某一堆K我们先只给它划分所需要的一部分重量 那么要想形成它所需要的质量此时需要把某一堆O的质量分给它。 从而需要O本身的质量进行划分这样的话肯定是没有直接整堆划分更优的 3、为什么优先对3堆进行合并而不是2堆 这里选择优先合并3堆 因为假想一下有三堆总和是sz。把它划分为三堆花销即是sz。 但是如果合并两堆这时需要先使用sz的花销划分为两堆a和b。 然后还需要min(a,b)来把两堆形成我们需要的三堆
AC代码
#include math.h
#include stdio.h
#include algorithm
#include cstring
#include iostream
#include queue
using namespace std;
const int N 2e5 10;
#define de(x) cout x ;
#define sf(x) scanf(%d, x);
#define Pu puts();
#define ll long long
ll n, m, ans;
priority_queuell, vectorll, greaterll q;
int main() {cin n;// 首先这里按照每堆所正好含有的数量进行划分是最优的// 因为假想我们对于某一堆K我们先只给它划分所需要的一部分重量// 那么要想形成它所需要的质量此时需要把某一堆O的质量分给它。// 从而需要O本身的质量进行划分这样的话肯定是没有直接整堆划分更优的ll x;for (int i 1; i n; i) {scanf(%lld, x);q.push(x);}m 3;// 这里选择优先合并3堆// 因为假想一下有三堆总和是sz。把它划分为三堆花销即是sz。// 但是如果合并两堆这时需要先使用sz的花销划分为两堆a和b。// 然后还需要min(a,b)来把两队形成我们需要的三堆while ((n - 1) % (m - 1)) {q.push(0ll); // 特别巧妙n;}ans 0;ll t, sz;while (q.size() 1) {sz 0;for (int i 1; i m; i) {t q.top();q.pop();sz t;}q.push(sz);ans sz;}de(ans);return 0;
}
