爆搜过十万(误)。

题目链接

先二分第$n$大是几。

如何check呢？

首先可以写一个搜索，如果它搜出了$n$个$\ge mid$的方案，那肯定答案肯定$\ge mid$，否则答案$< mid$。

然而这个算法是指数级的。

可以加一个剪枝，如果没有确定的数组都选最大值还是只能$< mid$，那就退出。

分析一下这个算法的复杂度，在搜索树上一共有$n$个叶节点，这个搜索只会访问这$n$个叶节点的祖先。

所以这样的复杂度是$O(nk)$。（变成多项式的了，可喜可贺）

如果把搜索树上只有一个孩子的节点和它的孩子合并，那么搜索树上的节点个数就是$O(n)$的了。

也就是说在搜到一个点的时候，需要跳过只能选最大值、不能选次大值的那些数组。

那么可以将这$k$个数组按照最大值$-$次大值从小到大排序。这样的话，如果当前数组只能选最大值、不能选次大值，那么之后的数组也都不行，这种情况可以直接跳到叶节点。

这样check的复杂度就变成$O(n)$的了。

假设二分出来的答案是$ans$，如何输出答案呢？

使用上面的方法搜出$\ge ans + 1$的所有解，这样会搜出不到$n$个值，剩下的值一定全都是$ans$。

复杂度$O(n \log v)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
int n, k;
vector<ll> a[maxn + 10], b;
ll s[maxn + 10];

bool cmp(const vector<ll> &a, const vector<ll> &b) {
	return a[0] - a[1] < b[0] - b[1];
}

void dfs(int p, ll sum, ll lim) {
	if (sum + s[p] < lim) return;
	if (p == k + 1) b.push_back(sum);
	else {
		if (sum + s[p] - a[p][0] + a[p][1] < lim) dfs(k + 1, sum + s[p], lim);
		else {
			for (int i = 0; i < (int)a[p].size(); ++i)
				if (sum + a[p][i] + s[p + 1] < lim) return;
				else {
					dfs(p + 1, sum + a[p][i], lim);
					if ((int)b.size() == n) return;
				}
		}
	}
}

int main() {
	scanf("%d%d", &k, &n);
	for (int i = 1; i <= k; ++i) {
		int m; scanf("%d", &m);
		while (m--) {
			int x; scanf("%d", &x);
			a[i].push_back(x);
		}
		a[i].push_back(-1e18);
		sort(a[i].begin(), a[i].end(), greater<ll>());
	}
	sort(a + 1, a + k + 1, cmp);
	for (int i = k; i >= 1; --i) s[i] = s[i + 1] + a[i][0];
	ll l = 0, r = 1e18, ans;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		b.clear(); dfs(1, 0, mid);
		if ((int)b.size() == n) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	b.clear(); dfs(1, 0, ans + 1);
	sort(b.begin(), b.end(), greater<ll>());
	for (int i = 0; i < (int)b.size(); ++i)
		printf("%lld ", b[i]);
	for (int i = 1; i <= n - (int)b.size(); ++i)
		printf("%lld ", ans);
}