HDOJ5884 二分+哈夫曼树

最新推荐文章于 2020-04-08 15:46:34 发布

罗侯

最新推荐文章于 2020-04-08 15:46:34 发布

阅读量390

点赞数

分类专栏：哈夫曼树文章标签：哈夫曼编码

本文链接：https://blog.csdn.net/computer_user/article/details/77868465

版权

哈夫曼树专栏收录该内容

2 篇文章

订阅专栏

Sort

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3139 Accepted Submission(s): 778

Problem Description

Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob

N sorted sequences, and the

i -th sequence includes

ai elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than

k sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than

T cost. So Bob wants to know the smallest

k to make the program complete in time.

Input

The first line of input contains an integer

t0 , the number of test cases.

t0 test cases follow.
For each test case, the first line consists two integers

N (2≤N≤100000) and

T (∑Ni=1ai<T<231) .
In the next line there are

N integers

a1,a2,a3,...,aN(∀i,0≤ai≤1000) .

Output

For each test cases, output the smallest

k .

Sample Input

Sample Output

Source

2016 ACM/ICPC Asia Regional Qingdao Online

Recommend

wange2014 | We have carefully selected several similar problems for you: 6193 6192 6191 6190 6189

不用二分的话肯定超时。。

多叉的哈夫曼树就是二叉的哈夫曼树的扩展，加条循环语句就OK了。。

对于每个k，总共需要归并n-1个数，每次归并k-1个数，所以当(n-1)%(k-1)!=0的时候，会出现归并不能最大化个数的情况。用零补齐就OK了。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define ll  long long
using namespace std;

const int maxn = 1e5+5;
int a[maxn];
int n,t,i,j,k;

void init(){
    scanf("%d %d",&n,&t);
    for (i=0; i<n; i++) scanf("%d",&a[i]);
    sort(a,a+n);
}

bool huffman(int k) {
    queue<ll>p;
    queue<ll>q;
    int mod = (n-1)%(k-1);
    if (mod!=0) {for (i=0; i<k-1-mod; i++) p.push(0); }
    for (i=0; i<n; i++) p.push(a[i]);
    ll ans = 0;
    while (!p.empty() || !q.empty()) {
         ll sum = 0;
         for (i=0; i<k; i++) {
            if (p.empty() && q.empty()) break;
            if (p.empty()) {sum += q.front(); q.pop();}
            else if (q.empty()) {sum+=p.front(); p.pop();}
            else if (p.front()<q.front()) {
                 sum += p.front();
                 p.pop();
            }
            else {sum+=q.front(); q.pop();}
         }
         ans += sum;
         if (p.empty() && q.empty()) break;
         q.push(sum);
    }
    if (ans>t) return 0;
    return 1;
}

int main(){
    int T;
    scanf("%d",&T);
    while (T--) {
        init();
        int s = 2, e = n ,mid;
        while (s<e) {
            mid = (s+e)/2;
            if (huffman(mid)) e = mid;
            else s = mid+1;
        }
        printf("%d\n",s);
    }
    return 0;
}