HDU5884 Sort

題意：有n個(gè)序列要進(jìn)行歸并，每次歸并的代價(jià)是兩個(gè)序列的長度的和，要求最終的代價(jià)不能超過規(guī)定的T，求在此前提下一次能同時(shí)進(jìn)行歸并的序列的個(gè)數(shù)k。

思路：還是太單純，看完題目一直以為要用歸并排序來解題，如果已經(jīng)看過多叉哈夫曼樹的知識(shí)的話估計(jì)就不會(huì)這樣了。先二分查找這個(gè)k，然后用多叉哈夫曼樹來判斷這個(gè)k是不是還能再變小。用兩個(gè)隊(duì)列來實(shí)現(xiàn)多叉哈夫曼樹。

PS：如果不進(jìn)行提前處理的話，最后一次的歸并可能就湊不齊k個(gè)來了，所以需要提前處理一下。

代碼：

#include <iostream> #include <cstdio> #include <algorithm> #include <set> #include <queue> using namespace std; const int maxn = 1e5 + 100; typedef long long ll; //typedef pair<int,int> P; queue<ll> q1; queue<ll> q2; int T,n; ll a[maxn]; ll t;bool Hufman(int x) {while (!q1.empty()) q1.pop();while (!q2.empty()) q2.pop();int tt = (n - 1) % (x - 1);if (tt){for (int i = 1; i <= x - 1 - tt; i++)//添加虛構(gòu)0，使得最后一次能湊齊k個(gè)序列，手動(dòng)模擬了一下求tt的過程，q1.push(0);//但不明白n-1具體的原因，不知是不是固定的模式 }for (int i = 1; i <= n; i++)q1.push(a[i]);ll sum = 0;while (1){ll tem = 0;for (int i = 1; i <= x; i++){if (q1.empty() && q2.empty())break;if (q1.empty()){tem += q2.front();q2.pop();}else if (q2.empty()){tem += q1.front();q1.pop();}else{int tx, ty;tx = q1.front();ty = q2.front();if (tx < ty){tem += tx;q1.pop();}else{tem += ty;q2.pop();}}}sum += tem;if (q1.empty() && q2.empty())break;q2.push(tem);//q2這個(gè)序列一定是有序的 }if (sum <= t)return 1;elsereturn 0; }int main() {scanf("%d", &T);while (T--){scanf("%d%lld", &n, &t);for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);sort(a + 1, a + 1 + n);int st = 2, en = n;while (st < en){int mid = (st + en) / 2;if (Hufman(mid))en = mid;elsest = mid + 1;//printf("GG\n"); }printf("%d\n", st);}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/sykline/p/9737772.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Sort HDU5884（二分+多叉哈夫曼树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。