首页 > 代码库 > codeforces733D. Kostya the Sculptor 偏序cmp排序，数据结构hash,代码简化

codeforces733D. Kostya the Sculptor 偏序cmp排序，数据结构hash,代码简化

2024-08-21 00:03:53   222人阅读

对于n==100。1,1,2或者1,2,2大量重复的形状相同的数据，cmp函数最后一项如果表达式带等于，整个程序就会崩溃

还没有仔细分析std::sort的调用过程，所以这里不是很懂。。，mark以后研究

因为题目让你挑一到两个平行六面体，然后去每个平行六面体长宽高的最小值，然后去求最小值中的最大值

我们很容易想到暴力的做法，如果两个平行六面体能够合并的话，那我们直接计算合并之后的最小值，因为我们知道此时

合并之后再求最小值，它是只增不减的

那么我们就要找到能合并某一个面的所有平行六面体的集合，

这里有一个令人模糊的地方，那就是对于每一个平行六面体，我们选它的哪一个面呢，当然只有三个不同的面

我们发现了以下事实

1,2,3==3,2,1==2,3,1尺寸的平行六面体是同一个东西，但是这个给我们带来了很大的困扰。。

因为我们会把同一个东西当成不同的考虑3遍，而每一遍我们起初还会考虑三个面。。很乱。。

但是仔细一想，我们其实不用考虑1,2和1,3这两个面，因为你叠加这两个平行六面体，只增加次大值或者最大值

最小值没变。。而只有最小值对答案有贡献，所以说我们要让除了最小值的另外两个尺寸构成平面然后去考虑能不能和其他的

平行六面体叠加，增加最小值，从而达到增大对答案贡献的目的

所以我们需要把每个平行六面体的size从小到大排序，然后我们希望对平行六面体整体排序，然后次大值和最大值相等的尽量挨在一起

这样就好处理了，这个就是字典序了，看你侧重哪个元素的优先选取，仔细想想就能懂了

本次代码经验，记得切换目录到源文件根目录，否则会报错。。能用数组索引操作的变量（下标操作）我们就尽量不起别名，用for简单操作

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
const int maxn=1e5+7;
struct node{
    int a[3];
    int index;
};
bool cmp(node a,node b){
    if(a.a[2]!=b.a[2]){
        return a.a[2]<b.a[2];
    }
    if(a.a[1]!=b.a[1]){
        return a.a[1]<b.a[1];
    }
    // if(a.a[2]!=b.a[2]){
    //     return a.a[2]<b.a[2];
    // }
    return a.a[0]<b.a[0];
    //全部相等的时候因该返回什么
    //目前我是这么理解的
    //如果cmp为真则sort不交换，如果sort为假那我们就交换
    //当完全相等的时候，我认为没有什么必要交换
    //我们应该按照2,1,0的顺序来排列？
    //事实证明有等于号好像不行呢。。

}

node A[maxn];
bool check(int pre,int next){
    node a=A[pre],b=A[next];
    if(a.a[1]==b.a[1]&&a.a[2]==b.a[2]) return true;
    return false;
}
int main(){
    scanf("%d",&n);
    register int i;
    //int temp[3];
    // printf("there1\n");
    for(i=0;i<n;++i){
        scanf("%d%d%d",&A[i].a[0],&A[i].a[1],&A[i].a[2]);
        sort(A[i].a,A[i].a+3);
        A[i].index=i+1;
    }
    // printf("there2\n");
    sort(A,A+n,cmp);
    //debug
    // for(i=0;i<n;++i){
    //     printf("p:%d %d %d\n",A[i].a[0],A[i].a[1],A[i].a[2]);
    // }
    // printf("there3\n");
    int ans,first=1;
    int ans1=-1,ans2=-1;
    for(i=0;i<n;++i){
        // printf("there4 i:%d\n",i);
        int mi=A[i].a[0];
        if(first){
            first=0;
            ans=mi;
            ans1=A[i].index;
            ans2=-1;//第一次初始化的时候更新不全
        }
        else{
            if(mi>ans){
                ans=mi;
                ans1=A[i].index;
                ans2=-1;
            }
        }
        if(i+1<n&&check(i,i+1)){
            int now=A[i].a[0]+A[i+1].a[0];
            mi=min(A[i].a[1],min(A[i].a[2],now));
            if(mi>ans){
                ans=mi;
                ans1=A[i].index;
                ans2=A[i+1].index;
            }
        }
    }
    if(ans2==-1){
        printf("1\n%d\n",ans1);
    }
    else{
        printf("2\n%d %d\n",ans1,ans2);
    }
    return 0;
}

 

codeforces733D. Kostya the Sculptor 偏序cmp排序，数据结构hash,代码简化


联系
我们