Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4449 Accepted Submission(s): 1098
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
题意
给出一个n个数的序列,现在要求最小的k满足 每次最多取出k个数进行合并且合并的总代价小于等于t
合并的代价被认为是合并序列的和。
题解
我们考虑二分来解决这个问题
二分一个k
如果我们使用优先队列每次选出k个数进行合并，这是最优的合并方式。
当然这必须满足每次取数恰好为k个。否则需要把多出来的数提前合并了。
通过(n-1) % (k-1) 进行判断
使用优先队列的check需要O(nlogn)时间复杂度。
总共需要O(nlognlogn)的时间复杂度，对于题给数据优化下输入勉强能卡过去。
代码
/**
* 二分 mid O(logn) check O(nlogn) 时间复杂度 O(nlognlogn)
* 100000 * log(100000) * log(100000) = 2e7
* 1s TLE
*
* 同时需要注意的是贪心的时候,对于不能每次都保证取k次能取光的时候,我们需要将多余的先优先合并了。
* 如 (n-1) % (k-1) == 0 表示每次都能保证只取k个。
* 否则需要先将 (n-1) % (k-1) + 1 个先合并了。
* 为什么是这样的呢,我们这么来考虑这个问题,每次取k个合并完后又要放进一个，相当于每次只取走了k-1个。
* 同时合并只剩下1个的时候停止，于是是(n-1)
* 综上 考虑 (n-1) % (k-1) 即可
*
* 考虑单调队列优化这个问题
*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > qu;
const int maxn = 1e5+10;
ll arr[maxn],t;
int n;
namespace IO
{
template <typename T>
inline bool scan_d (T &ret)
{
char c;
int sgn;
if (c = getchar(), c == EOF)return false; //EOF
while (c != '-' && (c < '0' || c > '9') )
if((c = getchar()) == EOF) return false;
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return true;
}
template<typename T>
void print(T x)
{
static char s[33], *s1;
s1 = s;
if (!x) *s1++ = '0';
if (x < 0) putchar('-'), x = -x;
while(x) *s1++ = (x % 10 + '0'), x /= 10;
while(s1-- != s) putchar(*s1);
}
template<typename T>
void println(T x)
{
print(x);
putchar('\n');
}
};
bool check(int k)
{
ll ans = 0;
while(!qu.empty()) qu.pop();
for(int i=1;i<=n;i++) qu.push(arr[i]);
int ma = (n-1) % (k-1);
if(ma) {
ll temp = 0;
for(int i=1;i<=ma+1 && !qu.empty();i++) temp += qu.top(),qu.pop();
ans += temp;
qu.push(temp);
}
while(!qu.empty()) {
ll temp = 0;
for(int i=1;i<=k && !qu.empty();i++) temp += qu.top(),qu.pop();
ans += temp;
if(!qu.empty()) qu.push(temp);
//if(ans > t) return false;
}
return ans <= t;
}
int main()
{
int caset;IO::scan_d(caset);
while(caset--) {
IO::scan_d(n);IO::scan_d(t);
for(int i=1;i<=n;i++) IO::scan_d(arr[i]);
std::sort(arr+1,arr+1+n); //先排序，减少建堆时间
int l = 2,r = n;
while(l <= r) {
int mid = (l+r)>>1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
IO::println(l);
}
return 0;
}
