题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5884
nn个有序序列的归并排序.每次可以选择不超过kk个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过TT, 问kk最小是多少
用一个队列维护合并的数，二分一下判断合理性。注意一点的是要是(n - 1)%(k - 1) != 0的话，就要先合并前(n - 1)%(k - 1) + 1项，这样会更优一点。还有细节问题很多要注意。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 #include <queue> 14 using namespace std; 15 typedef long long LL; 16 typedef pair <int, int> P; 17 const int N = 1e5 + 5; 18 LL a[N], m; 19 int n; 20 21 bool judge(int k) { 22 queue <int> que; 23 while(!que.empty()) { 24 que.pop(); 25 } 26 int sum = 0, i = 1; 27 if((n - 1)%(k - 1)) { 28 for( ; i <= (n - 1) % (k - 1) + 1; ++i) { 29 sum += a[i]; 30 } 31 que.push(sum); 32 } 33 int ans = sum; 34 for(; i <= n || !que.empty(); ++i) { 35 if(que.size() <= 1 && i > n) 36 break; 37 int cnt = k, ok = 0; 38 sum = 0; 39 while(cnt--) { 40 if((que.size() && que.front() < a[i])|| i > n) { 41 sum += que.front(); 42 que.pop(); 43 } else { 44 ok = 1; 45 sum += a[i++]; 46 } 47 } 48 if(ok) { 49 --i; 50 } 51 ans += sum; 52 que.push(sum); 53 } 54 return ans <= m; 55 } 56 57 int main() 58 { 59 int t; 60 scanf("%d", &t); 61 while(t--) { 62 scanf("%d %lld", &n, &m); 63 for(int i = 1; i <= n; ++i) { 64 scanf("%lld", a + i); 65 } 66 sort(a + 1, a + n + 1); 67 int l = 1, r = n; 68 while(l < r) { 69 int mid = (l + r) / 2; 70 if(judge(mid)) { 71 r = mid; 72 } else { 73 l = mid + 1; 74 } 75 } 76 printf("%d ", r); 77 } 78 return 0; 79 }