http://codeforces.com/contest/752/problem/E
首先有一个东西就是，如果我要检测5，那么14我们认为它能产生2个5.
14 = 7 + 7.但是按照平均分的话，它是不能产生5的，那就把那两个7当成是两个5，因为7比5还大，对min(b[i])是没有影响的。
可以思考下样例2.
那么二分答案mid,设dp[val][x]表示val这个数字能产生多少个x。dp[val][x] = dp[val / 2][x] + dp[(val + 1) / 2][x]
那么dp数组开不了那么大，可以考虑记忆化搜索。用另外一个数组vis[]标记是否已经搜索过即可。因为dp数组需要重复使用，已经有值了。vis[]可以用DFN简单代替memset
判断每个数字能拆成多少个x，复杂度是logn的，所以复杂度是nlognlogn
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e6 + ;
int a[maxn];
int n, k;
int dp[maxn * ];
int vis[maxn * ];
int DFN;
int func(int val, int x) {
if (vis[val] == DFN) return dp[val];
if (val < x) return ;
if (val / < x) { // 6也算可以生成5
vis[val] = DFN;
dp[val] = ;
return ;
}
if (val & ) {
int ans = func(val / , x) + func((val + ) / , x);
vis[val] = DFN;
dp[val] = ans;
return ans;
} else {
int ans = * func(val / , x);
vis[val] = DFN;
dp[val] = ans;
return ans;
}
}
bool check(LL val) {
int ans = ;
++DFN;
for (int i = ; i <= n; ++i) {
if (a[i] < val) break;
ans += func(a[i], val);
if (ans >= k) return true;
}
return false;
}
void work() {
scanf("%d%d", &n, &k);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + , a + + n, greater<int>());
// for (int i = 1; i <= n; ++i) {
// cout << a[i] << " ";
// }
// cout << endl;
LL be = , en = 1e14L;
while (be <= en) {
LL mid = (be + en) >> ;
if (check(mid)) {
be = mid + ;
} else en = mid - ;
}
if (en == ) {
printf("-1\n");
} else printf("%I64d\n", en);
// cout << func(20, 5) << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}