1. 首页
2. 二分
3. 本页

HDU 5884 Sort (二分+队列)

题目链接：点我~~

题意：$n$个有序序列的归并排序.每次可以选择不超过$k$个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问$k$最小是多少。

思路：先对所有数排序，另外一个队列维护合并后的值，取值时从两个序列前端取小的即可。如果$(n-1)mod(k-1)\ne 0$，要把最小的$(n-1)\%(k-1)+1$个数先合并一下。剩下的恰好可以每次合并k个数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 1000100;

int n,t;
int a[100000+100];

int solve(int k)
{
    queue<int >q;
    int cnt=0,ans=0;
    int res=0;
    int c=(n-1)%(k-1);
    if(c)
    {
        while(cnt<=c)
            res+=a[cnt++];
        ans+=res;
        q.push(res);
    }
    while(1)
    {
        res=0;
        for(int i=0; i<k; ++i)
        {
            if(cnt<n &&(q.empty()||a[cnt]<q.front()))
                res+=a[cnt++];
            else
            {
                res+=q.front();
                q.pop();
            }
        }
        ans+=res;
        if(ans>t)
            return false;
        if(cnt>=n && q.empty())
            break;
        q.push(res);
    }
    return ans<=t;
}

void binfd(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(solve(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d\n",l);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&t);
        for(int i=0; i<n; ++i)
            scanf("%d",&a[i]);
        sort(a,a+n);
        binfd(1,n);
    }
    return 0;
}