[ARC105C] Camels and Bridge 题解

标签：ARC105C std le limits Bridge 题解 valueType 重物 max

题意

给定 \(N\) 个重物，其中第 \(i\) 个重物的重量为 \(w_i\)。现在要将其排成一排，可以任意指定相邻两个重物的距离。

同时给定 \(M\) 个限制，其中第 \(i\) 个限制为 \((l_i, v_i)\)，表示要求不存在长度为 \(l_i\) 的线段，使得其包括的重物重量之和大于 \(v_i\)。

最小化重物间的最大距离或报告无解。

• \(2 \le N \le 8\)
• \(1 \le M \le 10^5\)
• \(1 \le w_i, l_i, v_i \le 10^8\)

题解

首先，若 \(\max\limits_{i = 1}^{N} w > \min\limits_{i = 1}^{M} v_i\)，那么一定无解，反之一定有解。下文中假设一定有解。

由于 \(N\) 的值很小，所以可以考虑枚举重物之间的排列顺序，然后依次计算 \(N!\) 种排列的最小化的最大距离。

考虑如何计算，不妨设 \(f_{i}\) 表示第 \(i\) 个重物到第一个重物的最小距离，那么有转移

\[f_{i} = \max\limits_{j = 1}^{i - 1} \left\{f_j + L\left(\sum\limits_{k = j}^{i}w_i\right)\right\} \]

其中 \(L(x)\) 表示一段总重量为 \(x\) 的线段的最短长度。

现在问题转化为了如何快速求出 \(L(x)\)，发现 \(L(x)\) 可以表示为：

\[\max\limits_{1 \le i \le M \land v_i \le x} l_i \]

因此我们可以将所有限制按 \(v_i\) 的大小升序排序，那么求 \(L(x)\) 时只需要二分出最大的满足 \(v_i \le x\) 的 \(i\) 后查询前缀最大值即可。

时间复杂度 \(\mathcal{O}(N!N^2\log M + M \log M)\)，空间复杂度 \(\mathcal{O}(N + M)\)，可以通过。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector W(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> W[i];

    PairVector A(M + 1);

    for (valueType i = 1; i <= M; ++i)
        std::cin >> A[i].second >> A[i].first;

    {
        valueType maxW = std::numeric_limits<valueType>::min(), minV = std::numeric_limits<valueType>::max();

        for (valueType i = 1; i <= N; ++i)
            maxW = std::max(maxW, W[i]);

        for (valueType i = 1; i <= M; ++i)
            minV = std::min(minV, A[i].first);

        if (maxW > minV) {
            std::cout << -1 << std::endl;

            return 0;
        }
    }

    std::sort(A.begin() + 1, A.end());

    ValueVector max(M + 1, 0);

    for (valueType i = 1; i <= M; ++i)
        max[i] = std::max(max[i - 1], A[i].second);

    auto calc = [&](valueType sum) -> valueType {
        valueType l = 1, r = M, ans = 0;

        while (l <= r) {
            valueType mid = (l + r) / 2;

            if (A[mid].first < sum) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return max[ans];
    };

    ValueVector P(N + 1, 0);

    std::iota(P.begin(), P.end(), 0);

    valueType ans = std::numeric_limits<valueType>::max();

    do {
        ValueVector F(N + 1, 0);

        F[0] = 0;
        for (valueType i = 1; i <= N; ++i) {
            F[i] = 0;

            valueType sum = W[P[i]];

            for (valueType j = i - 1; j >= 1; --j) {
                sum += W[P[j]];

                F[i] = std::max(F[i], F[j] + calc(sum));
            }
        }

        ans = std::min(ans, F[N]);
    } while (std::next_permutation(P.begin() + 1, P.end()));

    std::cout << ans << std::endl;
}

标签：ARC105C,std,le,limits,Bridge,题解,valueType,重物,max
From： https://www.cnblogs.com/User-Unauthorized/p/solution-ARC105C.html