题解：P12258 [蓝桥杯 2024 国 Java B] 背包问题

· · 题解

题目传送门

前言

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

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

思路

容易发现每次取最小可行的背包重量，然后通过分别加上 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)。