題目鏈接 http://acm.hdu.edu.cn/showproblem.php?pid=5884 Problem Description Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob ...
題目鏈接
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; }
