信息与未来 2024真题解析- 数据排序

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

题目描述

在计算机世界中，“表格”是一种简单、基础而且十分通用的数据结构，在数据库、人工智能等领域中都有广泛的应用。表格由若干行、若干列的单元格组成：

CSV (Comma-Separated Values) 是一种常用的表格格式。Dr. X 需要你编程处理简化的 CSV 文 件，格式规定如下：

CSV 文件包含

行数据，其中第一行是标题行。

CSV 文件每行一个字符串，对应了表格的一行。行中的单元格由半角逗号分隔。

每个单元格至少包含一个字符。单元格有两种类型：

数值单元格：由至少一个数字字符

组成。

字符串单元格：由数字字符

和大小写字母

组成,且至少包含一个字母。

标题行的所有单元格都是字符串单元格，且互不相同。标题行中包含了列的名称。

以下是一个 CSV 文件的示例：

Name,p1,p2,p3,Score

ZhangSan,40,30,28,98

LiSi,40,28,30,98

WangWu,40,25,20,85

你的任务是根据指定的列为表格中的行排序。例如根据Score- , Name+ , p3-排序意味着：

优先按 Score 列从大到小排序。Score 列都是数值单元格，因此按数值排序。

如果 Score 列相同，按 Name 列从小到大排序。Name 列都是字符串单元格，因此按照字典排序。

如果 Score 和 Name 列都相同，按 p3 列从大到小排序。p3 列都是数值单元格，因此按数 值排序。

我们保证 CSV 文件每一行的单元格数量相同，且除标题行外，每一列要么全是数值单元格，要么全是字符串单元格。

输入格式

输入数据分为两部分。第一部分描述了 CSV 表格：

第一行一个整数

，表示 CSV 文件的行数（包含标题行）。

接下来

行,每行一个字符串，描述 CSV 表格中的行。

第二部分描述了排序要求:

第一行一个整数

，表示排序依据列的数量。

接下来

行，每行一个字符串，按顺序给出了排序依据的列名及排序方式（加号或减号）。加号代表升序排列、减号代表降序排列。

输出格式

输出

行，为排序后的 CSV 表格（包含标题行）。对于所有排序依据列的值都相同的行，保持它们在输入文件中的相对顺序。

输入输出样例 #1

输入 #1

4

Name,p1,p2,p3,Score

ZhangSan,40,30,28,98

LiSi,40,28,30,98

WangWu,40,25,20,85

3

Score-

Name+

p3-

输出 #1

Name,p1,p2,p3,Score

LiSi,40,28,30,98

ZhangSan,40,30,28,98

WangWu,40,25,20,85

说明/提示

对于

的数据，满足

，表格不超过

列，字符串单元格不超过

个字符，且数值单元格中的数值是

到

之间的整数。

本题原始满分为

。

题目分析

题目要求对一个CSV文件的行按照指定的列和排序方式进行排序。CSV文件的格式如下：

第一行是表头，表头中的每个单元格都是字符串，且互不相同。

从第二行开始是数据行，每行的单元格可以是数值或字符串。

排序规则由多列和排序方式（升序或降序）组成。

解题步骤

1. 读取CSV文件

输入表头

第一行是表头，读取后存储到一个字符串数组h中。

使用一个lambda表达式（匿名函数）解析字符串，按逗号分隔单元格。

输入数据行

从第二行开始，逐行读取数据行，存储到一个Row结构体数组r中。

每个Row包含一个字符串数组c（表示单元格数据）和一个索引idx（表示原始行号）。

同样使用lambda表达式解析每行数据。

2. 判断每列的数据类型

数值列检测

遍历每一列，检查是否所有单元格都是数值（即只包含数字字符）。

如果某列中存在非数值单元格，则该列标记为非数值列。

使用all_of函数检查每个单元格是否全部由数字字符组成。

存储列类型

使用一个布尔数组nc，其中nc[i]表示第i列是否为数值列。

3. 构建列索引映射

列名到索引的映射

使用一个哈希表ci，将表头中的列名映射到对应的列索引。

这样可以通过列名快速找到列索引。

4. 读取排序规则

解析排序规则

读取排序规则的数量m。

对于每个排序规则，提取列名和排序方式（升序或降序）。

将排序规则存储到一个元组数组c中，每个元组包含：

列索引

升序标志（true表示升序，false表示降序）

数值标志（true表示数值列，false表示字符串列）

5. 自定义排序

排序逻辑

使用sort函数对数据行进行排序，自定义排序规则。

对于每一对行a和b，按照排序规则逐列比较：

如果是数值列，将字符串转换为整数进行比较。

如果是字符串列，直接比较字符串。

根据升序标志决定比较的方向。

如果某列的值不同，则根据该列的比较结果决定行的顺序。

如果所有排序列的值都相同，则保持原始顺序（通过比较idx）。

6. 输出排序后的CSV文件

输出表头

按原样输出表头。

输出数据行

按排序后的顺序输出每行数据，单元格之间用逗号分隔。

参考题解代码：

#include <bits/stdc++.h>using namespace std;struct Row { vector<string> c; int idx; }; // 定义行结构，包含单元格数据和原始索引int main() {   int n; cin >> n; cin.ignore(); // 读取表格行数并忽略换行符   vector<string> h; // 存储表头   vector<Row> r; // 存储表格数据行   string s;   for (int i = 0; i < n; ++i) {       getline(cin, s); // 逐行读取数据       if (!i) h = [](string s) { // 如果是第一行，解析表头           vector<string> v; string t;           for (char c : s) c == ',' ? (v.push_back(t), t = "") : t += c;           v.push_back(t);           return v;       }(s);       else r.push_back({[](string s) { // 解析数据行           vector<string> v; string t;           for (char c : s) c == ',' ? (v.push_back(t), t = "") : t += c;           v.push_back(t);           return v;       }(s), i - 1});   }   vector<bool> nc(h.size(), 1); // 标记每列是否为数值列   for (int i = 0; i < h.size(); ++i)       for (auto& x : r) if (!all_of(x.c[i].begin(), x.c[i].end(), ::isdigit)) { nc[i] = 0; break; }   unordered_map<string, int> ci; // 列名到列索引的映射   for (int i = 0; i < h.size(); ++i) ci[h[i]] = i;   int m; cin >> m; cin.ignore(); // 读取排序规则数量   vector<tuple<int, bool, bool>> c; // 存储排序条件   while (m--) {       getline(cin, s);       string name = s.substr(0, s.size() - 1); // 提取列名       c.emplace_back(ci[name], s.back() == '+', nc[ci[name]]); // 存储列索引、升序标志和数值标志   }   sort(r.begin(), r.end(), [&](Row& a, Row& b) { // 自定义排序函数       for (auto& [i, asc, num] : c) { // 遍历排序条件           if (num) { // 如果是数值列               int x = stoi(a.c[i]), y = stoi(b.c[i]); // 转换为整数               if (x != y) return asc ? x < y : x > y; // 根据升序标志比较           } else if (a.c[i] != b.c[i]) return asc ? a.c[i] < b.c[i] : a.c[i] > b.c[i]; // 字符串列比较       }       return a.idx < b.idx; // 如果所有条件相同，保持原始顺序   });   for (int i = 0; i < h.size(); ++i) cout << (i ? "," : "") << h[i]; // 输出表头   cout << endl;   for (auto& x : r) { // 输出排序后的数据行       for (int i = 0; i < x.c.size(); ++i) cout << (i ? "," : "") << x.c[i];       cout << endl;   }}