HDU 5884-Sort（队列+二分）

来源：微智科技网

Sort

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

Problem Description

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

sorted sequences, and the

-th sequence includes

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

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

cost. So Bob wants to know the smallest

to make the program complete in time.

Input

The first line of input contains an integer

, the number of test cases.

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

and

.
In the next line there are

integers

Output

For each test cases, output the smallest

Sample Input

Sample Output

Source

Recommend

wange2014 | We have carefully selected several similar problems for you:

题目意思：

n个元素的序列做归并排序，每次可以选择不超过 $k$ 个序列进行合并,合并代价为这些序列的长度和，总的合并代价不能超过 $T$ , 求一个最小的 $k$ 。

解题思路：

先升序排列数组，再判断对于当前的k，序列能否被恰好分割。如果不能，就先取(n-1)%(k-1)+1个数归并一次；之后每次从两个队头取出k个数出来合并，判断与T的大小关系。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <queue>
#define maxn 200010
#define INF 0xfffffff
using namespace std;

int n;
long long x[maxn],T;
queue<int> que1,que2;
bool Valid(int k)
{
    long long sum=0,ans=0;
    while(!que1.empty()) que1.pop();//没有clear()所以只能手动清空
    while(!que2.empty()) que2.pop();
    for(int i=0; i<n; ++i)//把数组元素压入队列一
        que1.push(x[i]);
    if((n-1)%(k-1)!=0)//如果不能恰好分割
    {
        int num=(n-1)%(k-1)+1;
        for(int i=0; i<num; ++i)
        {
            sum+=que1.front();
            que1.pop();
        }
        que2.push(sum);
        ans+=sum;
    }
    //每次从两个队头取出k个数出来合并
    while(!que1.empty())
    {
        sum=0;
        for(int i=0; i<k; ++i)
        {
            if(!que1.empty() &&!que2.empty())
            {
                if(que1.front()<=que2.front())
                {
                    sum+=que1.front();
                    que1.pop();
                }
                else
                {
                    sum+=que2.front();
                    que2.pop();
                }
            }
            else if(que1.empty())
            {
                sum+=que2.front();
                que2.pop();
            }
            else if(que2.empty())
            {
                sum+=que1.front();
                que1.pop();
            }
        }
        ans+=sum;
        que2.push(sum);
    }
    if(ans>T) return false;//此时的k不满足
    sum=0;
    while(!que2.empty())
    {
        for(int i=0; i<k; ++i)
        {
            if(i==k-1)//保证取k个数
            {
                que2.push(sum);
                ans+=sum;
                sum=0;
            }
            if(que2.empty()) break;//不足k个数
            sum+=que2.front();
            que2.pop();
        }
    }
    if(ans>T) return false;
    return true;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%Id",&n,&T);
        for(int i=0; i<n; ++i)
            scanf("%Id",&x[i]);
        sort(x,x+n);//注意要先排个序
        int low=1,high=n-1,k,ans=1;
        while(low<=high)
        {
            k=(low+high)/2;
            if(Valid(k))//当前k满足条件，区间缩成左半边
            {
                high=k-1;
                ans=k;
            }
            else low=k+1;
        }
        printf("%d\n",ans);//当前k不满足条件，区间缩成右半边
    }
    return 0;
}

/*
1
5 25
1 2 3 4 5
*/

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

HDU 5884-Sort（队列+二分）

Sort

题目意思：

解题思路：