STL专题-sort、reverse

本文最后更新于：2021年2月4日 上午

引图

sort大法好👍

学习视频来源 网易云课堂：2018NEUQ-ACM蓝桥杯培训

sort——排序

sort函数是用于给定区间所有元素进行排序的函数，排序算法类似于快排，**时间复杂度n*log2(n)**，执行效率较高。

所在头文件 #include <algorithm>

sort函数：sort(first,last,cmp)

sort函数会对[first,last)区间内的数据按照cmp的方式进行排序。当不写cmp时按照默认排序方式——由小到大。

自定义排序方法1——自定义比较函数cmp

自定义比较函数cmp，要求形参类型要与排序的类型相一致。

  • 由小到大(默认排序方式)：如果认为第一个参数比第二个参数小，也就是第一个参数要排在第二个参数之前时返回true。

    1
    2
    3
    4
    bool cmp(int a,int b)
    {
    	return a<b;
    }

  • 由大到小：没什么记忆诀窍😭，就看自定义返回值的大于号还是小于号记忆吧。

    1
    2
    3
    4
    bool cmp(int a,int b)
    {
    	return a>b;
    }

    自定义排序方法2——重载比较运算符“<”

1
2
3
4
5
bool operator<(Student s1,Student s2)
{
    if(s1.name!=s2.name) return s1.name<s2.name;
    return s1.age<s2.age;
}

自定义排序方法3——声明比较类

引图

👍暂时不太理解。

例题 蓝桥杯——日期问题

问题描述

　　小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

　　比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

　　给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式
　　一个日期，格式是”AA/BB/CC”。 (0 <= A, B, C <= 9)

输出格式
　　输出若干个不相同的日期，每个日期一行，格式是”yyyy-MM-dd”。多个日期按从早到晚排列。

样例输入
02/03/04

样例输出

2002-03-04

2004-02-03

2004-03-02

数据规模和约定
　　峰值内存消耗（含虚拟机） < 256M
　　
　　CPU消耗 < 1000ms

题目分析

  1. 日期格式有年月日、月日年、日月年三种，而每种格式将日期扩展都会有19XX年和20XX年两种情况，也就是说输入一次会有六种日期生成。
  2. 生成日期会有不符合正常情况的日子存在，比如不在题目要求范围内，或者是闰年特殊的2月29日。
  3. 闰年：能被4整除但不能被100整除的普通闰年，以及能被400整除的世纪闰年两种。
  4. 输入格式是”AA/BB/CC”，注意读取数据的方式。可以采用scanf("%d/%d/%d",&AA,&BB,&CC);记得scanf的‘&’符号！
  5. 输出格式要求”yyyy-MM-dd”，即要求月份与日期必须是两位数。可以采用C++ iomanip控制输出格式(cout << date[i].year << "-" << setw(2) << setfill('0') << date[i].month << "-" <<setw(2) << setfill('0') <<date[i].day << endl;)，或者采用printf("%d-%02d-%02d\n",date[i].year,date[i].month,date[i].day)的方式。
  6. 去除不合理的日期也会有可能出现重复的日期，记得去重。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Date{
	int year;
	int month;
	int day;
};
//全局变量
Date date[10];
int nums = 0;//用于记录有几个正确日期

//重载‘<’
bool operator<(Date d1, Date d2)
{
	//日期从小到大
	if (d1.year != d2.year) return d1.year < d2.year;
	if (d1.month != d2.month) return d1.month < d2.month;
	return d1.day < d2.day;
}

//判断日期是否合理
bool judge(Date d)
{
	//创建月份数组，方便比较
	int mon[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
	if (d.year < 1960 || d.year>2059) return false;
	else if (d.month <= 0 || d.month > 12) return false;
	else if ((d.year % 400 == 0) || (d.year % 4 == 0 && d.year % 100 != 0))
	{		//闰年的判断方法
		if (d.month == 2) return d.day <= 29;
		else return d.day <= mon[d.month - 1] && d.day>0;
	}
	else return d.day <= mon[d.month - 1] && d.day>0;
}

//转换日期
void change(int a, int b, int c)
{
	Date d;
	d.year = a; d.month = b; d.day = c;
	if (judge(d))
	{
		date[nums] = d;
		nums++;
	}
}

int main()
{
	int a = 0, b=0, c = 0;
	scanf_s("%d/%d/%d", &a, &b, &c);//按照格式读取
	//年月日
	change(1900 + a, b, c);
	change(2000 + a, b, c);
	//日月年
	change(1900 + c, b, a);
	change(2000 + c, b, a);
	//月日年
	change(1900 + c, a, b);
	change(2000 + c, a, b);
	//排序
	sort(date, date + nums);
	//去重输出，也可用set等容器存储，不用再去重
	for (int i = 0; i < nums; i++)
	{
		if (date[i].year != date[i - 1].year || date[i].month != date[i - 1].month || date[i].day != date[i - 1].day)
		{
			cout << date[i].year << "-" << setw(2) << setfill('0') << date[i].month << "-" <<setw(2) << setfill('0') <<date[i].day << endl;
			//或者printf("%d-%02d-%02d\n",date[i].year,date[i].month,date[i].day);这样更加方便
		}
	}
	return 0;
}

reverse——逆序

属于C++头文件

1
#include <algorithm>

函数原型：

1
void reverse(first,end);

reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素）。

参考链接：C++ reverse函数的用法