@Dmaxiya 2020-08-24T23:49:12.000000Z 字数 8320 阅读 2077

排序 & 结构体排序练习题解

Hello_World

$sort$ 函数的使用

$sort$ 函数内部实现是快速排序，其功能是将传入的数组进行快速排序，时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(1)$ 。快排足以应对大多数题目，如果出现卡常数的题目，可以手写基数排序，这里不进行展开。
这里介绍一下几种简单的 $sort$ 函数的用法。

1. 对基本数据类型的数组进行默认排序

$sort$ 函数的默认排序规则是从小到大，如果对基本数据类型数组进行排序，则只要将数组的首地址作为函数的第一个实参，超尾地址作为函数的第二个实参，就可以对数组从第一个参数指向的地址到第二个参数指向的地址之间的元素进行排序。
超尾地址：数组最后一个元素的后一位，例如对于声明为

const int maxn = 100;
int num[maxn];

的整型数组，最后一个元素为

num[maxn - 1];

其超尾地址就是

&num[maxn];

也可以写为

num + maxn;

要对数组所有元素进行排序， $sort$ 函数的调用方式为

sort(num, num + maxn);

如果以

sort(num, num + n);

调用 $sort$ 函数，则对 $num$ 数组的前 $n$ 个元素从小到大排序。

2. 对基本数据类型按特定规则排序

$sort$ 函数的另一个重载形式，可以支持第三个参数：比较函数的传入，它会将比较函数应用在快速排序中，当比较函数返回值为 $true/非零值$ 时，第一个元素被认为比第二个元素小，当比较函数返回值为 $false/0$ 时，第一个元素被认为大于等于第二个元素，比较函数可以自定义，但是一定要注意：比较函数必须要定义小于号的意义，而不能定义小于等于号的意义。
以下是对 $num$ 整型数组所有元素进行绝对值从小到大排序的比较函数定义与 $sort$ 函数的调用方法：

const int maxn = 100;
int num[maxn];
bool cmp(int a, int b) {
    return abs(a) < abs(b);
}
sort(num, num + maxn, cmp);

利用比较函数，也可以对字符串进行快速排序：

const int maxn = 100000 + 100;
const int maxm = 1000 + 100;
char str[maxn][maxm];
int Index[maxn];
bool cmp(int a, int b) {
    return strcmp(str[a], str[b]) < 0;
}
sort(Index, Index + maxn, cmp);

我们知道，对于长度为 $1000$ 的字符串，排序过程中的赋值操作是很慢的，但是我们可以通过利用字符串做比较，对下标进行赋值，这样排序的速度将会降低 $O(len)$ ，其中 $len$ 为字符串的长度，排序结果存在 $Index$ 数组中，按照下面的方式可以输出正确的排序结果：

for(int i = 0; i < maxn; ++i) {
    printf("%s\n", str[Index[i]]);
}

3. 结构体排序

对于基本数据类型， $sort$ 函数的默认比较是利用小于号，但是对于自定义的结构体，语言本身不会给出结构体小于号的定义，所以我们可以自定义结构体的 $cmp$ 比较函数，用第 $2$ 点所说方法对结构体进行排序，但是我个人强烈建议定义结构体的小于号操作!
定义了结构体的小于号操作，在将结构体数组地址传入 $sort$ 函数时就不必再放入第三个参数， $sort$ 函数默认利用小于号比较，这里仍然要定义小于号操作，而不要定义小于等于操作，在后面的 $STL$ 中结构体只要定义了小于号，就可以不用管各种乱七八糟的重载了。下面给出日期结构体以月份为第一关键字，日期为第二关键字的定义小于号的写法：

struct Node {
    int month;
    int day;
};
bool operator<(const Node &a, const Node &b) {
    if(a.month == b.month) {
        return a.day < b.day;
    }
    return a.month < b.month;
}

另一种写法为：

struct Node {
    int month;
    int day;
    bool operator<(const Node &tmp) {
        if(month == tmp.month) {
            return day < tmp.day;
        }
        return month < tmp.month;
    }
};

第一种是将小于号作为结构体的友元函数，第二种是将小于号作为结构体的成员函数，具体的 C++ 语法细节自己去抠，但是请注意：
1. 在写小于号的形参传入时，用上

const Node &

类型，一是加快比较函数速度（引用传递的速度远远快过值传递），二是加强比较准确度（注意 $double$ 类型值传递过程中的精度损失）。
2. 不要定义小于等于操作，如下：

struct Node {
    int x;
};
bool operator<(const Node &a, const Node &b) {
    return a.x <= b.x;
}

这将会埋下很深的隐性错误，原因在于， $STL$ 中无法对该结构体定义等于操作，在 $STL$ 中将用以下方式定义等于操作：

bool operator==(const Node &a, const Node &b) {
    return !(a < b) && !(b < a);
}

其中的小于号规则，就是利用你所定义的小于号规则，你可以尝试将以上的代码逻辑运用到下面的程序中模拟一遍结果：

Node a, b;
a.x = 3;
b.x = 3;
if(a == b) {
    printf("yes");
} else {
    printf("no");
}

输出的结果将会是 $no$ ，所以请务必不要定义小于等于操作！

2 月 3 日排序练习题解

A. Ignatius and the Princess IV

题意

给定 $N$ （ $N$ 为奇数）个整数，其中有一个数字出现至少 $\frac{N+1}{2}$ 次，问这个数字是多少。

数据范围

$1\leq N\leq999999$

题解

将这 $N$ 个数字进行排序，则这个特殊的数字必然被连续地排在一起，又因为这个连续的数字长度占 $\frac{N+1}{2}$ ，所以它一定会出现在第 $\frac{N+1}{2}$ 的位置，排序后取位于 $\frac{N+1}{2}$ 位置上的数字就是这个特殊的数字。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
int n;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        sort(num, num + n);
        printf("%d\n", num[n / 2]);
    }
    return 0;
}

B. As Easy As A+B

题意

对 $T$ 组数据，每组数据第一个为 $N$ ，表示要对接下来 $N$ 个数字 $a_i$ 按升序排序后输出结果。

数据范围

$1\leq N\leq1000\\-2^{31}\leq a_i\leq2^{31}-1$

题解

按照 $sort$ 的默认排序进行排序后输出。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int T, n;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        sort(num, num + n);
        for(int i = 0; i < n; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", num[i]);
        }
        printf("\n");
    }
    return 0;
}

C. Rank

题意

给出 $Jackson$ 的学号，以及全班人的学号 $num_i$ 和成绩 $mark_i$ ，在有并列排名（有可能出现 $1~1~3~3~3~6$ 的排名情况）的情况下，问 $Jackson$ 的排名。

数据范围

$10000000\leq num_i\leq99999999\\0\leq mark_i\leq100$

题解

这题只要按照：以分数为主关键字，如果分数相同，学号和 $Jackson$ 相等排名靠前，就能得到 $Jackson$ 的排名，这里一定要注意当两个结构体元素相等时要返回 $false$ ，否则 $lower\_bound$ 函数就会失效。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int Num, Score;
struct Node {
    int num;
    int score;
    Node() {}
    Node(int n, int s) {
        num = n;
        score = s;
    }
};
bool operator<(const Node &a, const Node &b) {
    if(a.score == b.score) {
        if(a.num == b.num) {
            return false;
        }
        if(a.num == Num) {
            return true;
        } else if(b.num == Num) {
            return false;
        } else {
            return a.num < b.num;
        }
    }
    return a.score > b.score;
}
int s, n, ans;
vector<Node> vct;
vector<Node>::iterator it;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &Num) != EOF) {
        vct.clear();
        while(scanf("%d%d", &n, &s), n != 0 || s != 0) {
            vct.push_back(Node(n, s));
            if(n == Num) {
                Score = s;
            }
        }
        sort(vct.begin(), vct.end());
        it = lower_bound(vct.begin(), vct.end(), Node(Num, Score));
        printf("%d\n", it - vct.begin() + 1);
    }
    return 0;
}

2 月 4 日结构体排序练习题解

A. Solving Order

题意

$T$ 组数据，每组数据有 $n$ 种气球，第 $i$ 种气球有 $num_i$ 个，按照气球个数输出气球颜色。

数据范围

$1\leq T\leq100,1\leq n\leq100\\ 1\leq\left|s\right|\leq10,1\leq\sum_i^nnum_i\leq83$

题解

将气球颜色字符串和气球个数放到一个结构体中，定义结构体的小于号运算符，按照 $num$ 值大的气球排在前面，排序后输出。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
struct Node {
    char str[maxn];
    int num;
};
bool operator<(const Node &a, const Node &b) {
    return a.num > b.num;
}
int T, n;
Node node[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%s%d", node[i].str, &node[i].num);
        }
        sort(node, node + n);
        for(int i = 0; i < n; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%s", node[i].str);
        }
        printf("\n");
    }
    return 0;
}

B. Design T-Shirt

题意

$n$ 个人对 $m$ 个选项投票， $num_{ij}$ 表示第 $i$ 个人对第 $m$ 项投的票数，问投票最多的 $k$ 项分别是哪几项，如果存在票数相同的项，优先选择下标小的项，将这些项按下标从大到小输出。

数据范围

$1\leq n,m\leq100,1\leq k\leq m$

题解

统计每一项获得的票数，将票数和项目下标记录在结构体中，定义结构体的小于号运算符，按照总票数为第一关键字，下标为第二关键字进行排序后，按下标从大到小输出。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
struct Node {
    int col;
    double num;
};
bool operator<(const Node &a, const Node &b) {
    if(a.num == b.num) {
        return a.col < b.col;
    }
    return a.num > b.num;
}
int n, m, k;
double tmp;
Node node[maxn];
int ans[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        memset(node, 0, sizeof(node));
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                scanf("%lf", &tmp);
                node[j].num += tmp;
                node[j].col = j;
            }
        }
        sort(node + 1, node + m + 1);
        for(int i = 1; i <= k; ++i) {
            ans[i] = node[i].col;
        }
        sort(ans + 1, ans + k + 1);
        for(int i = k; i > 0; --i) {
            if(i != k) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

C. Milk

题意

$Ignatius$ 每天都要喝 $200mL$ 牛奶，如果当天牛奶少于 $200mL$ 或者牛奶超过 $5$ 天，他都会把牛奶扔掉。今天 $Ignatius$ 要在 $n$ 种牛奶中挑一种，按照单价（平均每天的价格）便宜的买，如果两种牛奶单价相同，则买容量大的。

数据范围

$1\leq n\leq100,1\leq\left|s\right|\leq100$

题解

将牛奶的品牌、单价、容量放入一个结构体中，按题意计算出每种牛奶的单价，再按题意给的规则排序，输出第一项牛奶的品牌。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
struct Node {
    char str[maxn];
    double price;
    double vol;
    double per;
    Node() {}
    void Set() {
        int day = min(vol / 200, 5.0);
        per = price / day;
    }
};
bool operator<(const Node &a, const Node &b) {
    if(a.per == b.per) {
        return a.vol > b.vol;
    }
    return a.per < b.per;
}
int T, n;
Node node[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%s%lf%lf", node[i].str, &node[i].price, &node[i].vol);
            node[i].Set();
        }
        sort(node, node + n);
        printf("%s\n", node[0].str);
    }
    return 0;
}

排序 & 结构体排序练习题解

sort 函数的使用

1. 对基本数据类型的数组进行默认排序

2. 对基本数据类型按特定规则排序

3. 结构体排序

2 月 3 日 排序练习题解

A. Ignatius and the Princess IV

题意

数据范围

题解

过题代码

B. As Easy As A+B

题意

数据范围

题解

过题代码

C. Rank

题意

数据范围

题解

过题代码

2 月 4 日结构体排序练习题解

A. Solving Order

题意

数据范围

题解

过题代码

B. Design T-Shirt

题意

数据范围

题解

过题代码

C. Milk

题意

数据范围

题解

过题代码

内容目录

$sort$ 函数的使用

2 月 3 日排序练习题解