Codeforces 733D 立方體（想法題）

題目：http://codeforces.com/contest/733/problem/D

題意：

給定n個長方體，求一個最大的内切球的半徑，可以是兩塊石頭将兩個完全比對的面合起來的或者就用一塊石頭，輸出切出最大内切球的那1/2個石頭是哪些。

分析：

一個立方體得到一個球，那麼限制球半徑大小的是最小的邊長。

考慮一個立方體，那麼最優一定是max(min(a[i],b[i],c[i]))

考慮2個立方體，如果想更大，一定是去合并最小的邊，使最小邊變大，這樣答案就有可能變大。

要想合并最小的邊，那麼另外兩條邊就要相等。是以先按照另外兩條邊排序，這樣在判斷一下兩個立方體的兩條邊是否相等，如果相等在判斷是否合并後更大即可。

比賽的時候想複雜了，認為對于目前i立方體，二分找到他可以合并的最小邊最大的那個立方體，然後再合并這兩個。其實根本沒必要，因為最優的情況，一定是相臨的2個可以合并的立方體，因為排序後肯定最小的邊遞增嘛（在可以合并的一段中）。

是以下面的代碼把二分去掉，直接判斷i和i+1是否可以合并即可。

看到一種很簡單的方法：（來自：blog.csdn.net/fsss_7/article/details/52995389）

我們先考慮用一塊石頭的最大内切球半徑，一定是ans=max(min(a,b,c))。令a<=b<=c，那麼如果我們想用兩塊石頭來優化ans那麼一定需要兩塊石頭的b1c1和b2c2那個面，因為如果在這個合并的面内有a的話那麼答案一定不會更優，是以我們用一個二維map存一下之前map[b][c]的最大的a即可，然後去判斷合并的min(a+map[b][c],b)是否能更新ans即可。

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int INF=;
const int N=+;
int s[N];
int a[],n;
struct point
{
    int a,b,c,idx;
    bool operator < (const point& rhs)const{
        if(c==rhs.c&&b==rhs.b)return a<rhs.a;
        if(c==rhs.c)return b<rhs.b;
        return c<rhs.c;
    }
};
point p[N],p1[N];

int powb(int x,int y,int v)
{
    int m;
    while(x<y){
        m=x+(y-x+)/;
        if(p[m].b<=v)x=m;
        else y=m-;
    }
    return x;
}
int powc(int x,int y,int v)
{
    int m;
    while(x<y){
        m=x+(y-x+)/;
        if(p[m].c<=v)x=m;
        else y=m-;
    }
    return x;
}
int main()
{
    //freopen("f.txt","r",stdin);
    scanf("%d",&n);
    int ans=;
    int idx1,idx;
    for(int i=;i<=n;i++){
        scanf("%d%d%d",&a[],&a[],&a[]);
        sort(a,a+);
        p[i].a=a[];
        p[i].b=a[];
        p[i].c=a[];
        p[i].idx=i;

        if(a[]>ans)ans=a[],idx=i;
    }
    sort(p+,p++n);
    bool flag=;
    for(int i=;i<=n;i++){
        //cout<<p[i].c<<' '<<p1[i].c<<endl;
        int x=powc(i,n,p[i].c);
        int y=powb(i,x,p[i].b);
        if(y>i&&(ans<p[i].a+p[y].a&&ans<p[i].b)){
            flag=;
            ans=min(p[i].b,p[i].a+p[y].a);
                idx=p[i].idx;
                idx1=p[y].idx;
        }
    }
    if(flag){
        puts("2");
        printf("%d %d\n",idx,idx1);
    }
    else{
        puts("1");
        printf("%d\n",idx);
    }
    return ;
}