2016 年青島網絡賽---Sort(k叉哈夫曼)，2016---sort

2016 年青島網絡賽---Sort(k叉哈夫曼)，2016---sort

題目鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=5884

 

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 1 5 25 1 2 3 4 5   Sample Output 3   Source 2016 ACM/ICPC Asia Regional Qingdao Online     Recommend wange2014   |   We have carefully selected several similar problems for you:  5891 5890 5889 5887 5886    題意：to組數據，每次輸入N，T，然後輸入N個數，進行合並操作，將其中k個數合並為一個數後，代價為這k個數的和，並將這個和放入剩余的數列中，一直合並下去......最後合並為一個數，要求總的代價不超過T，求最小的k值；   思路：k叉哈夫曼樹，很明顯k值在2~N之間，而且k越大總的代價越小，那麼利用這個性質我們可以對k值進行二分查找，我開始時想的用優先隊列做，但超時了......我們可以對數組先從小到大排序，然後利用一個隊列裝合並得到的數，每次取數組和隊列中較小的數，注意用一個變量pos記錄數組取完數後的下一個位置，隊列中取完數後要刪除這個數，為什麼可以這樣呢？ 因為每次合並得到的數一定小於等於上次合並得到的數，所以最小數一是 數組pos位置和隊列首中的較小者。另外，這些數的個數不一定滿足k個k個的合並，所以要先合並不足的幾個數，什麼時候不滿足呢，（N-1）%(k-1)!=0 時；   代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <cmath>
#include <string.h>
using namespace std;
int N;
long long T;
long long a[100005];

int calc(int k)
{
    queue<long long>q;
    int pos=0;
    long long sum=0;
    if((N-1)%(k-1)!=0&&N>k) ///如果不能k個k個合並到底，則先合並籌不足k個的；
    {
        pos=(N-1)%(k-1)+1;
        for(int i=0;i<pos;i++)  sum+=a[i];
        q.push(sum);
    }
    while(1)
    {
        long long sum2=0;
        for(int i=0; i<k; i++)
        {
            if(!q.empty())
            {
                if(pos<N&&q.front()>a[pos])
                {
                    sum2+=a[pos];
                    sum+=a[pos];
                    pos++;
                }
                else
                {
                    sum2+=q.front();
                    sum+=q.front();
                    q.pop();
                }
            }
            else if(pos<N)
            {
                sum2+=a[pos];
                sum+=a[pos];
                pos++;
            }
            else goto endw;
        }
        if(sum>T) return 0;
        if(pos<N||!q.empty())
        q.push(sum2);
    }
    endw:;
    if(sum<=T) return 1;
    else    return 0;
}

int main()
{
    int to;
    scanf("%d",&to);
    while(to--)
    {
        scanf("%d%lld",&N,&T);
        for(int i=0; i<N; i++)
            scanf("%lld",&a[i]);
        sort(a,a+N);
        int l=2,r=N,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            int f=calc(mid);
            if(f==0) l=mid+1;
            else     r=mid-1;
        }
        printf("%d\n",l);
    }
    return 0;
}