Codeforces 733D Kostya the Sculptor

发表于 分类于 Disqus：

链接

传送门

题意

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

思路

内接球的大小由长方体最短的棱决定，所以每次拼接只有延长最短的棱才有意义，用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;
}