20221115_T4B_折半搜索双指针

题意

市面上共有 \(n\) 张门票，方便起见，我们把它们从 \(1\) 至 \(n\) 编号。其中，\(i\) 号门票对应的场次为第 \(b_i,1\leq b_i\leq k)\)场，价格为 \(c_i\) 元，且座位的排数为 \(p_i\)。
现在，Yazid 共有 \(m\) 元的总预算，他打算在不超出预算的情况下，购买到 \(k\) 张排数总和最小的门票。
请你帮帮 Yazid 挑选合适的门票，方便起见，你只需输出这个最小总排数即可。

数据范围 \(n\leq 100, k \leq 12, m, c_i \leq {10}^9\)

题解

赛时得分 50/100 （打的暴力，挂了 10 分）

这明显是一个不可 dp 的背包。我们考虑如何优化搜索。

我们可以将两个背包合并起来，我们尝试将 \(12\) 个背包合并成 \(2\) 个。

这两个枚举中间所有东西，按照 \(v\) 排序，因为排序之后 \(i\) 从小到大扫描 \(v\) 满足条件的从大到小。所以复杂度是集合大小的。

所以总时间复杂度是一个集合大小的，应该是 \(\mathcal{O}(\Big(\frac{n}{k}\Big)^k)\) 的，差不多为 \(8^6\) 可以通过本题。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

vpii a, b;
vpii obj[13];
int T, n, m, k;

vpii trans(vpii x, vpii y) {
    vpii res;
    res.clear();
    for(auto [w1, v1] : x) 
        for(auto [w2, v2] : y) 
            if(w1 + w2 <= m) res.push_back(make_pair(w1 + w2, v1 + v2));
    return res;
}

signed main() {
    freopen("ticket.in", "r", stdin);
    freopen("ticket.out", "w", stdout);
    read(T);
    while(T--) {
        read(n, m, k);
        a.clear(), b.clear();
        for(int i = 1; i <= k; ++i) obj[i].clear();
        for(int i = 1; i <= n; ++i) {
            int bl, w, v;
            read(bl, w, v);
            obj[bl].push_back(make_pair(w, v));
        }
        a.push_back(make_pair(0, 0));
        b.push_back(make_pair(0, 0));
        for(int i = 1; i <= k; ++i) {
            if(a.size() > b.size()) swap(a, b);
            a = trans(a, obj[i]);
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        if(a.size() == 0 || b.size() == 0) {
            puts("No solution");
            continue;
        }
        int minn = inf, ans = inf;
        for(int i = a.size() - 1, j = 0; i >= 0; --i) {
            while(j < b.size() && b[j].first + a[i].first <= m) {
                minn = min(minn, b[j].second);
                ++j;
            }
            if(j == 0) continue;
            ans = min(ans, minn + a[i].second);
        }
        if(ans >= inf) {
            puts("No solution");
            continue;
        }
        cout << ans << endl;
    }
    return 0;
}