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

主题思路

估算一下模拟的时间复杂度为

O(n\log{n}\times m)

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

CPP

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 排序代码。

CPP

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 后，我们再写一行代码就完成了排序。

CPP

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

最后输出就行了。

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

文章操作

主题思路

相关推荐

评论

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