Hdu 5884

hdu 5884 Sort

题意：

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

解法：

1：首先想到的是二分这个答案k，然后check每个k是否可行

2：对于每个k，总共需要归并n-1个数，每次归并k-1个数

所以当(n-1)%(k-1)!=0的时候，会出现归并不能最大化个数的情况，这样会影响二分的单调性

我们先取(n-1)%(k-1)个小的数凑成一次k，接下来的数我们已经知道了肯定是(n-1)/(k-1)块了，所以可以直接想到放进优先队> 列，然后每次都拿前k个数，新的数继续丢进去

CODE：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std; 

#define LL long long

#define N 200100

LL a[N],T,n,t;

queue<int> q1, q2;

inline bool check(int x) {

    while(!q1.empty()) q1.pop();

    while(!q2.empty()) q2.pop();

    for(int i = 1 ; i <= n ; i++)

        q1.push(a[i]);

    int num = 0;

    LL sum = 0,ans = 0;

    if((n - 1) % (x - 1) != 0) {

        num = (n - 1) % (x - 1) + 1;

        for(int i = 1 ; i <= num ; i++) {

            sum += q1.front();

            q1.pop();

        }

        q2.push(sum);

        ans += sum;

    }

    while(!q1.empty()) {

        sum = 0;

        for(int i = 1 ; i <= x ; i++) {

            if(!q1.empty() && !q2.empty()) {

                if(q1.front() <= q2.front()) {

                    sum += q1.front();

                    q1.pop();

                } else {

                    sum += q2.front();

                    q2.pop();

                }

            } else if(q1.empty()){

                sum += q2.front();

                q2.pop();

            } else if(q2.empty()){

                sum += q1.front();

                q1.pop();

            }

        }

        ans += sum;

        q2.push(sum);

    }

    if(ans > T) return false;

    sum = num = 0;

    while(!q2.empty()) {

        sum += q2.front();

        q2.pop();

        num++;

        if(num == x) {

            q2.push(sum);

            ans += sum;

            sum = num = 0;

            if(q2.size() == 1) break;

        }

    }

    if(ans > T) return false;

    else return true;

}

int main() {

    scanf("%lld",&t);

    while(t--) {

        scanf("%lld%lld",&n,&T);

        for(int i = 1 ; i <= n ; i++)

            scanf("%lld",&a[i]);

        sort(a + 1, a + n + 1);

        LL l = 2, r = n, mid, ans = 0;

        while(l <= r) {

            mid = (l + r) >> 1;

            if(check(mid)) {

                ans = mid;

                r = mid - 1;

            } else l = mid + 1;

        }

        printf("%lld\n", ans);

    }

    //system("pause");

    return 0;

}

巴特西

Hdu 5884

hdu 5884 Sort

题意：

解法：

CODE：

最新文章

热门文章