题解：AT_abc376_c [ABC376C] Prepare Another Box

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

题解：AT_abc376_c [ABC376C] Prepare Another Box

691 字

3 分钟

题解：AT_abc376_c [ABC376C] Prepare Another Box

2024-10-20

2026-10-27

题解

C艹

AtCoder

AtCoder Beginner Contest

浏览量加载中...

很好的一道二分答案题。

听说 CSP 考前写 tj 可以让 rp += inf？

注：下文中 $w$ 指物品重量序列， $x$ 指箱子容量序列。

先问个问题：为什么我上来就敢肯定这是个二分答案题？

或者说，单调性在哪儿？

非常简单：如果一个盒子的容量越大，能装下的东西就更多（废话）。那么如果 $v$ 不够用，可以扩大容量变成 $v + 1, v + 2 \cdots 10^9$ 。因为 $10^9$ 是上限不能再大了。

所以就可以准备二分啦~

问2：你怎么 check 这个答案呢？

题目告诉我们，一共只有 $n$ 个箱子，而物品也有 $n$ 个，而且一个箱子最多放一个物品，因此物品与箱子必须一一对应，不可以有空箱子。

其次，只有 $w_i \le x_j$ 时第 $i$ 个物品才能放进第 $j$ 个箱子。那么结论就出来，排完序之后，要求对于 $\forall 1 \le i \le n$ ，要求 $w_i \le x_i$ ，否则会导致箱子空掉，然后就不满足刚才的条件了 QaQ。

所以，思路就出来了：

二分新增箱子容量
扫一遍，看看新增后是否合法

总的时间复杂度是 $O(n \log k)$ ，其中 $k = 10 ^ 9$ 。

然后，然后就结束啦~

ACCode:

1
/*Code by Block_Fish*/
2
#include <bits/stdc++.h>
3

4
#define INF 0x3f3f3f3f
5
#define EPS 1e-8
6
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
7
#define log printf
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<int, int> PII;
18

19
const int N = 2e5 + 10;
20
int n, a[N], b[N], c[N];
21

22
template <typename T>
23

24
inline T read() {
25
  T sum = 0, fl = 1;
26
  char ch = getchar();
27
  for (; !isdigit(ch); ch = getchar())
28
    if (ch == '-') fl = -1;
29
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
30
  return sum * fl;
31
}
32

33
template <typename T>
34

35
inline void write(T x) {
36
  if (x < 0) {
37
    putchar('-'), write<T>(-x);
38
    return;
39
  }
40
  static T sta[35];
41
  int top = 0;
42
  do { sta[top++] = x % 10, x /= 10; } while (x);
43
  while (top) putchar(sta[--top] + 48);
44
}
45

46
int chk(int q) {
47
  b[n] = q;
48
  sort(b + 1, b + n + 1);
49
  FOR(i, 1, n) if (a[i] > b[i]) {
50
    for (int j = 1; j < n; ++j) b[j] = c[j];
51
    // 注意要清空数组，因为排序会打乱顺序，因此不能直接将b[n]设为0，只能新开数组重新复制了 QwQ
52
    return false;
53
  }
54
  for (int j = 1; j < n; ++j) b[j] = c[j];
55
  return true;
56
}
57

58
int main() {
59
  n = read<int>();
60
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
61
  for (int i = 1; i < n; i++) scanf("%d", &b[i]), c[i] = b[i];  // 是<哦~
62
  sort(a + 1, a + n + 1);
63
  int l = 1, r = 1e9, ret = -1;  // 要求箱子是正整数个，从 1 开始
64
  while (l <= r) {
65
    int mid = (l + r) >> 1;
66
    if (chk(mid)) {
67
      ret = mid;
68
      r = mid - 1;
69
    } else l = mid + 1;
70
  }
71
  write<int>(ret);
72
  return 0;
73
}