http://codeforces.com/contest/733/problem/D
给定n个长方体，然后每个长方体都能选择任何一个面，去和其他长方体接在一起，也可以自己一个，要求使得新的长方体的最短的那条边最大。
看样例2就知道，因为10、8、7和10、8、2组合后，min = 8，是最大的。
那么怎么做呢？
可以看到，一个长方体，能产生6种不同的摆放方式，然后排序后，排序的时候把a相同的尽可能排在一起，把b相同的尽可能地排在一起。因为这样就能分组了。
把数组分成若干组，相同的组里，a和b的值是一样的，（当然也可能是同一个id产生的不同放法，判断时需要排除相同id）
然后开始贪心了，在同一个组里，选两个出来，使得加起来的C最大（因为a和b固定了）。就是选两个最大的C了。
选的时候要注意，不能选同一id的，
而且：允许两个最大的C是相等的，这是个坑，不要认为mx1一定要>mx2.
接下来就是排除相同id的情况了，可以用Mx[id]表示这个id的最大值，然后判断过一次后，就vis掉就可以了。
FST。。感觉CF怎么一路都打不上去啊。唉，I so week。。。我要变强 ---- flag
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 2e6 + 20; bool book[maxn]; struct node { int a, b, c; int id; node(int aa, int bb, int cc, int f) : a(aa), b(bb), c(cc), id(f) {} node() {} bool operator < (const struct node & rhs) const { if (a != rhs.a) return a > rhs.a; else if (b != rhs.b) return b > rhs.b; else return c > rhs.c; } } arr[maxn], hehe[maxn]; int mx[maxn]; bool isok(struct node a, struct node b) { return a.a == b.a && a.b == b.b; } void work() { int n; scanf("%d", &n); int tot = 0; int ans = 0; int p1, p2; int k = 1; for (int i = 1; i <= n; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); arr[++tot] = node(a, b, c, i); arr[++tot] = node(a, c, b, i); arr[++tot] = node(b, a, c, i); arr[++tot] = node(b, c, a, i); arr[++tot] = node(c, a, b, i); arr[++tot] = node(c, b, a, i); int h = min(a, min(b, c)); if (h > ans) { ans = h; p1 = i; } } sort(arr + 1, arr + 1 + tot); int to = 1; hehe[to] = arr[1]; for (int i = 2; i <= tot + 1; ++i) { //tot + 1，因为最后一组 if (isok(arr[i - 1], arr[i])) { hehe[++to] = arr[i]; } else { for (int j = 1; j <= to; ++j) { mx[hehe[j].id] = max(mx[hehe[j].id], hehe[j].c); } int mx1 = 0, mx2 = 0, id1 = 0, id2 = 0; for (int j = 1; j <= to; ++j) { if (book[hehe[j].id]) continue; if (mx1 <= mx[hehe[j].id]) { mx2 = mx1; id2 = id1; mx1 = mx[hehe[j].id]; id1 = hehe[j].id; } else if (mx2 <= mx[hehe[j].id]) { mx2 = mx[hehe[j].id]; id2 = hehe[j].id; } book[hehe[j].id] = 1; } int mi = min(hehe[1].a, hehe[1].b); mi = min(mi, mx1 + mx2); if (mi > ans && id1 != id2 && id1 && id2) { ans = mi; p1 = id1; p2 = id2; k = 2; } for (int j = 1; j <= to; ++j) { mx[hehe[j].id] = 0; book[hehe[j].id] = 0; } to = 1; hehe[to] = arr[i]; } } if (k == 1) { cout << k << endl; cout << p1 << endl; } else { cout << k << endl; cout << p1 << " " << p2 << endl; } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }