使用std::vector自带重载的比较运算符

lr580 发表于 3年前 · 关联问题 排名

这是一篇基于 C++ 语法的题解

以下展示一种非结构体的写法;事实上用结构体也是一样的,即把 sum,name,s 绑在一个结构体里,每次 std::swap 直接交换结构体即可。

重要知识: std::vector 重载了比较运算符,即 < , <= 等;规则为:对比较双方,依次比较每个元素(按元素的比较运算符规则,如 std::vector<int> 就按数值大小, std::vector<string> 就按字典序),直到可以区分为止。不难发现,这个比较规则刚好就是题意的排序规则第二点,所以我们可以直接调用该运算符,不需要再自己写 for 来逐个遍历各科分数。

热知识: std::swap 可以交换任意数据类型,复杂度取决于要交换的这个数据规模;因此对换时直接 std::swap 即可。也不需要开一个 for 对每个元素来交换。

为了便于(C++的)初学者理解,这里使用冒泡排序,不使用重载比较函数+快速排序(std::sort)等其他知识。 //想看这个的讨论区右转 bobby 的题解 >_<

参考代码:(我知道你们只看这个qwq)

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, m, sum[1010]; string name[1010]; vector<ll> s[1010]; signed main() { cin >> n >> m; for (ll i = 0; i < n; ++i) { cin >> name[i]; for (ll j = 0, v; j < m; ++j) { cin >> v; s[i].emplace_back(v); sum[i] += v; } } for (ll i = 0; i < n; ++i) { for (ll j = n - 1; j > i; --j) { if (sum[j] > sum[j - 1] || (sum[j] == sum[j - 1] && s[j] > s[j - 1])) { swap(sum[j], sum[j - 1]); swap(s[j], s[j - 1]); swap(name[j], name[j - 1]); } } } for (ll i = 0; i < n; ++i) { cout << name[i] << ' '; } return 0; }

冷知识: std::vectoremplace_back 函数略快于 push_back ,用法稍有不同。具体参考谷歌等搜索引擎。

如有错误,欢迎斧正 awa