Codeforces 733D Kostya the Sculptor

链接

传送门

题意

给出一些长方体,可以选一个长方体或两个有一面相同的长方体粘在一起变成一个大长方体。问使长方体内接球最大的选法。

思路

内接球的大小由长方体最短的棱决定,所以每次拼接只有延长最短的棱才有意义,用map存一下最短边的长度搞一搞就好啦。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 100010;
int a, b, c;
map<pii, pii> dict;
int main() {
int n, Max = 0, ans = 0, x = 0, y = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &a, &b, &c);
if (a < b) {
swap(a, b);
}
if (a < c) {
swap(a, c);
}
if (b < c) {
swap(b, c);
}
if (c > Max) {
ans = 1;
x = i;
Max = c;
}
pii k = make_pair(a, b);
pii& v = dict[k];
if (v.Y != 0) {
int cur = min(b, v.X + c);
if (cur > Max) {
ans = 2;
x = v.Y;
y = i;
Max = cur;
}
}
if (v.X < c) {
v = make_pair(c, i);
}
}
printf("%d\n", ans);
if (ans == 1) {
printf("%d\n", x);
} else {
printf("%d %d\n", x, y);
}
return 0;
}

支付宝扫码领红包