题解:AT_abc376_c [ABC376C] Prepare Another Box

Leo2011 魔怔哥

很好的一道二分答案题。

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

注:下文中 指物品重量序列, 指箱子容量序列。


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

或者说,单调性在哪儿?

非常简单:如果一个盒子的容量越大,能装下的东西就更多(废话)。那么如果 不够用,可以扩大容量变成 。因为 是上限不能再大了。

所以就可以准备二分啦~


问 2:你怎么 check 这个答案呢?

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

其次,只有 时第 个物品才能放进第 个箱子。那么结论就出来,排完序之后,要求对于 ,要求 ,否则会导致箱子空掉,然后就不满足刚才的条件了 QaQ。

所以,思路就出来了:

  1. 二分新增箱子容量

  2. 扫一遍,看看新增后是否合法

总的时间复杂度是 ,其中

然后,然后就结束啦~


ACCode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*Code by Leo2011*/
#include <bits/stdc++.h>

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

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

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

template <typename T>

inline T read() {
T sum = 0, fl = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}

template <typename T>

inline void write(T x) {
if (x < 0) {
putchar('-'), write<T>(-x);
return;
}
static T sta[35];
int top = 0;
do { sta[top++] = x % 10, x /= 10; } while (x);
while (top) putchar(sta[--top] + 48);
}

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

int main() {
n = read<int>();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) scanf("%d", &b[i]), c[i] = b[i]; // 是<哦~
sort(a + 1, a + n + 1);
int l = 1, r = 1e9, ret = -1; // 要求箱子是正整数个,从 1 开始
while (l <= r) {
int mid = (l + r) >> 1;
if (chk(mid)) {
ret = mid;
r = mid - 1;
} else l = mid + 1;
}
write<int>(ret);
return 0;
}

AC 记录~

理解万岁!

  • 标题: 题解:AT_abc376_c [ABC376C] Prepare Another Box
  • 作者: Leo2011
  • 创建于 : 2024-10-20 14:12:45
  • 更新于 : 2024-10-20 18:23:44
  • 链接: https://www.leo2011.eu.org/2024/10/20/ti-jie-at-abc376-c-abc376c-prepare-another-box/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
题解:AT_abc376_c [ABC376C] Prepare Another Box