自动搬运

查看原文

来自洛谷，原作者为

	zyzxzhangyi 不拿蓝√不改签

搬运于2025-08-24 23:14:05，当前版本为作者最后更新于2025-08-05 13:35:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前言

本蒟蒻不会楼下大佬的平衡树做法，故发表此篇题解。

本题和这道题类似，做完此题可以把它一起做了。

思路

容易发现每次取最小可行的背包重量，然后通过分别加上 $N$ 个商品的重量生成新的背包重量，执行 $L$ 次后就是第 $L$ 小的背包重量。

我们可以用数据结构来维护取最小的背包重量，堆再合适不过了，注意优先队列要存储两个值，一个是背包重量，一个是物品数量，物品数量要大于等于 $K$ 才是可行的。

操作时记得用二维 map 去重。

代码

#include <bits/stdc++.h>
using namespace std;

long long n, k, l, a[15];
struct note{
	long long v, s;
	bool operator < (note _) const{
		return v > _.v;
	}
}x;
priority_queue <note> q;
map <long long, map <int, bool> > t;

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 
	cin >> n >> k >> l;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) q.push({a[i], 1});
	while(l){
		x = q.top(), q.pop();
		if(x.s >= k) l--;
		for(int i = 1; i <= n; i++)
            if(!t[x.v + a[i]][min(k, x.s + 1)])
                 t[x.v + a[i]][min(k, x.s + 1)] = 1, q.push({x.v + a[i], x.s + 1});//记得取min
	}
	cout << x.v << endl;
	return 0;
}

AC记录

时间复杂度：$O(L \log {NL})$。

空间复杂度：$O(NL)$。