洛谷官方题单——排序题解（水题警告）

排序的题目基本都大同小异，按照题目给的规则排序即可，这里牵扯到的是stl的sort函数，sort函数一般我们都是这么使用的 ：

sort(a.begin(),a.end());

但是在某些时候，由于需要自定义排序顺序所以我们会这么使用：

sort(a.begin(),a.end(),cmp);

其中cmp是函数指针，具体的语言细节不用太过纠结，只需要知道这里为什么可以这么用了（牵扯到C++的一些细节，想了解的自行查阅函数缺省）。
如果想要从大到小排序（因为默认是从小到大排序），只需要如下两种方法。

//method 1
sort(arr, arr + 5, greater<int>());
//method 2
bool cmp(int x,int y){
    return x > y;
}

题目0：选举学生会

裸排序题，直接sort。

#include<algorithm>
#include<iostream>
using namespace std;
int memo[2000000];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>memo[i];
    sort(memo,memo+m); 
    for(int i=0;i<m;i++)
        cout<<memo[i]<<" ";
    return 0;
}

题目1：快速排序

模板题，虽然现在我们大家都是在使用sort函数，但是快排的精髓还是需要了解的，这里直接略过模板，建议直接在洛谷题解中学习。
重点是学习如何划分，和快排的算法思想——分治和贪心。

题目2：求第 k 小的数

分析下复杂度，n小于等于500W，时间限制1s，说明我们必须使用的是O(n)的算法或者常数较小的O(nlogn)算法，所以直接sort排序肯定GG。
这里使用STL的库函数十分的方便，如下所示，但是题目肯定不是为了让我们采用这些技巧，因此我们需要选择其他的方法。

    nth_element(memo,memo+k,memo+n);
    printf("%d",memo[k]);

这里选择的方法是采用分治的思想：遍历一遍数组，然后随机选择一个数（这里就看你怎么选啦，一般都是去中间比较方便），然后计算比中间数字大的放右边，小的放左边，相等的也放右边；这个时候看我们选择的数字的当前位置pos：
a. 如果pos==k，直接输出；b. 如果pos>k，则对左半部分进行同样的操作（递归）；c. 如果pos<k，则对右半部分进行相同操作。

#include<stdio.h>
long long memo[5000010];
int quicksort(int left, int right){
    int mid = memo[left];
    while (left < right){
        while (left < right && mid <= memo[right]) right--;
        memo[left] = memo[right];
        while (left < right && memo[left] <= mid) left++;
        memo[right] = memo[left];
    }
    memo[left] = mid;
    return left;
}
int find(int left, int right, int k){
    int pos = quicksort(left, right);
    if (k == pos) printf("%d", memo[k]);
    else if (k < pos) find(left, pos - 1, k);
    else find(pos + 1, right, k);
    return 0;
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d",&memo[i]);
    find(0, n - 1, k);
    return 0;
}

题目3：明明的随机数

这道题可以偷懒，直接采用set，也可以额外开一个数组来book是否有这个数。

#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
set<int>s;
int a[105];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    cout<<s.size()<<endl;
    while(!s.empty()){
        cout<<*s.begin()<<" ";
        s.erase(s.begin()); 
    }
    return 0;
 }

题目4：奖学金

简单的结构体排序，知道按照什么顺序就解决了——先比较总分，然后总分相同就优先比较语文，然后语文相同则比较输入顺序。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct Student{
    int List_Rank, Chinese, Math, English, Sum;
}Student;
Student memo[310];
bool cmp(Student a, Student b){
    if (a.Sum > b.Sum) return true;
    else if (a.Sum < b.Sum) return false;
    else{
        if (a.Chinese > b.Chinese) return true;
        else if (a.Chinese < b.Chinese) return false;
        else{
            if (a.List_Rank > b.List_Rank) return false;
            else return true;
        }
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        memo[i].List_Rank = i + 1;
        scanf("%d%d%d", &memo[i].Chinese, &memo[i].Math, &memo[i].English);
        memo[i].Sum = memo[i].Chinese + memo[i].Math + memo[i].English;
    }
    sort(memo, memo + n, cmp);
    for (int i = 0; i < 5; i++) printf("%d %d\n", memo[i].List_Rank, memo[i].Sum);
    return 0;
}

题目5: 宇宙总统

由于票数可能非常大，因此需要用string或者char数组，然后比较位数或直接比较string即可，char数组的话需要比较每一位大小。

#include <iostream>
#include <string>
using namespace std;
int main() {
    int num, id; 
    string max = "", temp_tickets;
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> temp_tickets;
        int inSize = temp_tickets.size(), maxSize = max.size();
        if (inSize > maxSize || (inSize >= maxSize && temp_tickets > max)) 
            max = temp_tickets, id = i;
    }
    cout << id+1 << endl << max << endl;
    return 0;
}

题目6：Bookshelf B

简单排序，由于要牛最小，只要从最大的开始减就行了，证明略。

#include<stdio.h>
#include<algorithm>
#include<functional>//greater
using namespace std;
int cow[20000];
int main(){
    int n, h, i;
    scanf("%d %d", &n, &h);
    for (i = 0; i < n; i++) scanf("%d", &cow[i]);
    sort(cow, cow + n, greater<int>());
    for (i = 0; h > 0; i++) h -= cow[i];
    return 0 * printf("%d", i);
}

题目7：车厢重组

等价于求逆序对，对于逆序对应用最多的就是冒泡排序，即使用冒泡排序（排序引理有关于逆序对和排序的关系，有兴趣可以去看《算法导论》)。

#include<stdio.h>
int memo[10001];
int main(){
    int cnt = 0, num, temp;
    scanf("%d", &num);
    for (int i = 0; i < num; i++) scanf("%d", &memo[i]);
    for (int i = 0; i < num - 1; i++){
        for (int j = 0; j < num - 1; j++){
            if (memo[j] > memo[j + 1]){
                temp = memo[j + 1];
                memo[j + 1] = memo[j];
                memo[j] = temp;
                cnt++;
            }
        }
    }
    return 0 * printf("%d", cnt);
}

题目8：欢乐的跳

实际上就是枚举每个相邻元素的差并记录，然后从1到n逐步检验记录数组，若某个元素为0，则说明不快乐，否则快乐。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int memo[1005], book[1005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &memo[i]);
    for (int i = 1; i < n; i++)  book[i] = abs(memo[i] - memo[i + 1]);
    sort(book + 1, book + n);
    for (int i = 1; i < n; i++) if (book[i] != i) return 0 * printf("Not jolly\n");
    return 0 * printf("Jolly\n");
}

题目9：分数线划定

一如既往的结构体排序，基本了解题意就可以写了。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct Volunteer {
    int Num, Score;
}Volunteer;
Volunteer people[5000];
int cmp(Volunteer p1, Volunteer p2) {
    if (p1.Score > p2.Score) return true;
    else if (p1.Score == p2.Score) return p1.Num < p2.Num;
    else return false;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    m = floor(m * 1.5);
    for (int i = 0; i < n; i++) scanf("%d%d", &people[i].Num, &people[i].Score);
    sort(people, people + n, cmp);
    int Score_Line = people[m - 1].Score, Volunteer_Num = m;
    for (int i = m; i < n; i++) {
        if (people[i].Score == Score_Line) Volunteer_Num += 1;
        else if (people[i].Score < Score_Line) break;
    }
    printf("%d %d\n", Score_Line, Volunteer_Num);
    for (int i = 0; i < Volunteer_Num; i++)
        printf("%d %d\n", people[i].Num, people[i].Score);
    return 0;
}

题目10：攀爬者

结构体排序，对每个点的高度从小到大排序，最后求和。

#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define MAXN 50050
using namespace std;
typedef struct node {
    int x, y, z;
}coordinate;
coordinate memo[MAXN];
double distance(int x1, int x2, int y1, int y2, int z1, int z2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2) + pow(z1 - z2, 2));
}
bool cmp(node a, node b) {
    return a.z < b.z;
}
int main() {
    int n;
    double ans;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d%d", &memo[i].x, &memo[i].y, &memo[i].z);
    sort(memo, memo + n, cmp);
    for (int i = 1; i < n; i++)
        ans += distance(memo[i - 1].x, memo[i].x, memo[i - 1].y, memo[i].y, memo[i - 1].z, memo[i].z);
    return 0 * printf("%.3lf\n", ans);
}

题目11：生日

又是结构体排序，基本上和后面都是一样的。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef struct node {
    string name;
    int year, mon, day,input_num;
}person;
person memo[105];
bool cmp(person p1, person p2) {
    if (p1.year != p2.year)
        return p1.year < p2.year;
    else {
        if (p1.mon != p2.mon) 
            return p1.mon < p2.mon;
        else if (p1.day == p2.day && p1.mon == p2.mon) 
            return p1.input_num > p2.input_num;
        else if (p1.day != p2.day && p1.mon == p2.mon) 
            return p1.day < p2.day;
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> memo[i].name >> memo[i].year >> memo[i].mon >> memo[i].day;
        memo[i].input_num = i;
    }
    stable_sort(memo, memo + n, cmp);
    for (int i = 0; i < n; i++)
        cout << memo[i].name << endl;
    return 0;
}

题目12：拼数

也是结构体排序，尝试着用vector来写（玩）。这里注意千万别直接return a>b，例子：32和321，如果直接比较，321会大于32，但是这样就错了。

#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
#define MAXN 105
vector<string> ans;
bool cmp(string a, string b) { return a+b > b+a; }
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        ans.push_back(str);
    }
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < n; i++) cout << ans[i];
    return 0;
}

这些题基本都这样了，水题水的也差不多。