题意
给定 \(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;
}