sort() function: it is a sort function in c++ stl library. Learning to use this function can greatly save us from writing a sort function, such as bubble sort (O(n2)). Moreover, this sort function is written by quick sort, so the time complexity is O(nlogn), so it can also greatly reduce the program running time.
Note that the sorting range is [first, last], including first and excluding last.
Usage:
vector<int> a = {3,7,2,5,6,8,5,4};
sort(a.begin(),a.begin()+4); //Sort the first four and output 2 3 5 7 6 8 5 4
//sort(a.begin(),a.end()); // Sort from small to large, output 2 3 4 5 6 7 8
//sort(a.begin(),a.end(),less<int>()); // Output 2 3 4 5 6 7 8
//sort(a.begin(),a.end(),my_less); // Custom sorting, output 2 3 4 5 6 7 8
//sort(a.begin(),a.end(),greater<int>());// Sort from large to small, output 8 7 6 5 4 3 2
//sort(a.begin(),a.end(),my_greater); // Output 8 7 6 5 4 3 2Using the {cmp() function, sort() can also sort structures, for example:
struct Student{
char name[256];
int score; //fraction
};
bool cmp(struct Student* a,struct Student* b){//Sort by score from large to small
return a->score > b->score;
}
......
vector<struct Student*> list; //Define the list and save the student information in the list
......
sort(list.begin(), list.end(), cmp); //Sort by scoreGive two simple examples
Example 1: wrong ticket
Title Description
A secret related unit has issued certain bills and wants to recover them all at the end of the year.
Each ticket has a unique ID} number. The ID} numbers of all bills throughout the year are continuous, but the starting number of ID is randomly selected.
Due to the negligence of the staff, an error occurred when entering the ID number, resulting in a broken ID number and a duplicate ID number. Your task is to find out the "Id" of the broken number and the "Id" of the duplicate number through programming. (assuming that hyphenation cannot occur between the largest and smallest)
Enter description
The program is required to first input an integer N (N < 100) to represent the number of subsequent data lines.
Then read in the N} row data.
The length of each row of data is different. It is several (no more than 100) positive integers (no more than 10 ^ 5) separated by spaces.
Output description
The program is required to output ， 11 ， lines, including two integers ， m and N, separated by spaces.
Where, m ＾ represents the broken number ＾ ID, and n represents the duplicate number ＾ ID.
sample input
2 5 6 8 11 9 10 12 9
sample output
7 9
The idea is very simple. We just need to arrange the order with sort first, and we can find out the duplicate sign and hyphen through several conditional statements
The code is as follows:
#include <iostream>
#include<cstdio>
#include<cstring>
#include <string>
#include<algorithm>
using namespace std;
int st[10010];
int main()
{
int x;
int n;
int t = 0;
cin >> n;
for (int i = 0; i < n;)//input
{
cin >> x;
st[t++] = x;
if (getchar() == '\n')i++;
}
sort(st, st + t); //Call the sort function
int d, z;
for (int i = 0; i < t - 1; i++)
{
if (st[i] - st[i - 1] > 1)//If the subtraction of two adjacent numbers is greater than one
d = st[i - 1] + 1; //You can get a broken number
if (st[i] == st[i + 1])
{
z = st[i];
}
}
cout << d << " " << z;
return 0;
}
Example 2: scholarships
Title Description
A primary school has recently received a sponsorship and plans to give part of it to the top five students with excellent academic achievements. At the end of the term, each student has three grades: Chinese, mathematics and English. First, sort according to the total score from high to low. If the total scores of the two students are the same, then sort according to the Chinese scores from high to low. If the total scores and Chinese scores of the two students are the same, the students with small student number are required to be in the front. In this way, the ranking of each student is uniquely determined.
Task: first calculate the total score according to the scores of the three courses entered, then sort according to the above rules, and finally output the student number and total score of the top five students according to the ranking order. Note that the scholarships of each of the top five students are different, so you must sort them strictly according to the above rules. For example, in a correct answer, if the output data of the first two lines (two numbers per line: student number and total score) is:
7 279 5 279
The meaning of these two lines of data is that the student numbers of the two students with the highest total scores are No. 7 and No. 5 in turn. The total score of the two students is 279 (the total score is equal to the sum of the input scores of Chinese, mathematics and English), but the Chinese score of the student with student number 7 is higher. If your top two output data is:
5 279 7 279
It is treated as an output error and cannot be scored.
Enter description
Line ￠ 11 is a positive integer ￠ n\ (6 \leq n \leq 300)n (6 ≤ n ≤ 300), indicating the number of students participating in the selection.
Lines ＾ n+1n+1 ＾ 22 ＾ to ＾ n + 1 ＾ each line has ＾ 33 ＾ numbers separated by spaces, and each number is between ＾ 00 ＾ and ＾ 100100 ＾. The − 33 digits in line − jj − represent the scores of students with student number − j-1j − 1 in Chinese, mathematics and English. The student number of each student is numbered as ＾ 11 ~ nn (exactly the line number of the input data minus ＾ 11).
The data given are correct and do not need to be tested.
Output description
There are 55 ￠ lines in total. Each line is two positive integers separated by spaces, representing the student number and total score of the top 55 ￠ students in turn.
sample input
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98
sample output
6 265 4 264 3 258 2 244 1 237
The idea is also simple. The main idea is to learn to use the custom cmp() function to sort the structure using the sort() function
The code is as follows
#include<bits/stdc++.h>
using namespace std;
struct stu {
int id; //Student number
int c, m, e; //Language, number and foreign language
int sum;
}st[305];
bool cmp(stu a, stu b) {
if (a.sum > b.sum)
return true;
else if (a.sum < b.sum)
return false;
else { //a.sum == b.sum
if (a.c > b.c)
return true;
else if (a.c < b.c)
return false;
else { //a.c == b.c
if (a.id > b.id)
return false;
else return true;
}
}
}
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
st[i].id = i; //Student number
cin >> st[i].c >> st[i].m >> st[i].e;
st[i].sum = st[i].c + st[i].m + st[i].e; //Total score
}
sort(st + 1, st + 1 + n, cmp);
for (int i = 1; i <= 5; i++)
cout << st[i].id << ' ' << st[i].sum << endl;
return 0;
}