题解：B3982 [信息与未来 2024] 数据排序

_WHX985_ · 2025-01-23 15:18:55 · 题解

主题思路

估算一下模拟的时间复杂度为 O(n\log{n}\times m) 代如题目中的数据范围不会超时，所以考虑模拟。现在的问题是题目中的输入让人很苦恼，一大串输入一个空格都没有。其实解决这个问题很简单，因为每个信息都由逗号隔开，所以我们可以一找到逗号就提取信息，如下代码所示。

for(int i=1;i<n;i++){
  cin>>s;
  s+=",";
  string num="";
  for(int j=0;j<=s.size()-1;j++){
    if(s[j]==','){
      bs[++v]=num;
      num="";
    }else{
      num+=s[j];
    }
  }
}

同理，我们可以把条件也按此法剥离出来，这样我们就得到了所有数据，现在就可以排序了，用 sort 需要手写 cmp 下面是带注释的 cmp 排序代码。

bool cmp(int i,int j){
    for(int k=1;k<=m;k++){//一个一个列举输入的条件
        if(x[i][b[k]]!=x[j][b[k]]){//当两数需要排序
            if(op[k]=='+'){//按升序排序
                if(!f[b[k]]){
                    if(x[i][b[k]].size()!=x[j][b[k]].size()) return x[i][b[k]].size()<x[j][b[k]].size();//要排序的数长度不相等就可以直接让长度小的数排前面
                    else return x[i][b[k]]<x[j][b[k]]; //否则字典序小的排前面
                }
                else return x[i][b[k]]<x[j][b[k]]; 
            }
            else{//降序排列（和升序同样的原理）
                if(!f[b[k]]){
                    if(x[i][b[k]].size()!=x[j][b[k]].size()) return x[i][b[k]].size()>x[j][b[k]].size();
                    else return x[i][b[k]]>x[j][b[k]]; 
                }
                else return x[i][b[k]]>x[j][b[k]]; 
            }
        }
    }
    return i<j;//都不满足字典序小的排前面
}

写好 sort 中的 cmp 后，我们再写一行代码就完成了排序。

sort(a+1,a+n,cmp);

最后输出就行了。