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;
}
