kkbtrainingI

sort使用 一、简单排序1.基础12345678910111213141516171819202122//1.sort顺序排序：默认从小到大排序#include <iostream>#include <algorithm>using namespace std;int main(){ int num[55] = {0}; num[0] = 9; num[1] = 2; num[2] = -5; num[3] = 5; num[4] = 7; num[5] = 22; //使用sort函数对下标为(0, 5)数字的区间进行排序 sort(num, num + 6); for(int i = 0; i < 6; ++i){ cout << num[i] << endl; } cout << endl; return 0;} 2.仿函数12345678910111213141516171819202122//2.sort逆序排序：利用C++中的greater<int>()函数实现#include <iostream>#include <algorithm>using namespace std;int main(){ int num[55] = {0}; num[0] = 9; num[1] = 2; num[2] = -5; num[3] = 5; num[4] = 7; num[5] = 22; //重点:利用C++中的greater<int>()函数进行从大到小的排序 sort(num, num + 6, greater<int>()); for(int i = 0; i < 6; ++i){ cout << num[i] << endl; } cout << edl; return 0;&# ...

大统领投票 原题链接：http://oj.haizeix.com/problem/380 第一届地球大统领开始选拔，全地球的所有生物都积极参与投票，现在已知得票结果，请输出新当选的得票数最多的地球大统领的编号和得票数。 输入：输入第一行为一个整数 N 表示参选生物数。（1 ≤ N ≤ 100）接下来 N 行，每行一个整数，表示第 i 名参选生物的票数。票数不会超过 1000位。 输出： 输出得票数最多的生物的编号和票数。 样例： 1234312345679912345678913245678912345678911111111111111 122123456789132456789123456789 思路： 定义一个结构体包含某生物的编号与票数，使用sort方法对结构体排序后输出,时间复杂度: $O(nlogn)$ 遍历一遍所有生物，动态更新票数多的答案即可，时间复杂度: $O(n)$ 12345678910111213141516171819202122232425262728293031#include <iostream>#include <algorithm>#include <string>using namespace std;struct node{ int num; string score;};//当票数长度相同时，C++中已经重载了小于号可以直接使用进行字典顺序排序bool cmp(const node &a, const node &b){ if(a.score.size() == b.score.size()){ return a.score > b.score; } return a.score.size() > b.score.size();};node bio[105];int main(){ int n; cin >> n; for(int i = 1; i <= n; ++i){ cin >> bio[i].score; bio[i].num = i;
...

谁拿了最多奖学金 原题链接：http://oj.haizeix.com/problem/381 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 院士奖学金，每人 8000 元，期末平均成绩高于 80 分（>80），并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得； 五四奖学金，每人 4000 元，期末平均成绩高于 85 分（>85），并且班级评议成绩高于 80 分（>80）的学生均可获得； 成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（>90）的学生均可获得； 西部奖学金，每人 1000 元，期末平均成绩高于 85 分（>85）的西部省份学生均可获得； 班级贡献奖，每人 850 元，班级评议成绩高于 80 分（>80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高。 输入： 第一行是 1 个整数 N（1 ≤ N ≤ 100），表示学生的总数。 接下来的 N 行每行是一位学生的数据，从左向右依次是姓名、期末平均成绩、班级评议成绩、是否是学生干部、是否是西部省份学生、以及发表的论文数。 是否是学生干部和是否是西部省份学生分别用 1 个字符表示，Y 表示是，N 表示不是；发表的论文数是 0 到 10 的整数。 输出： 包括 3 行。 第 1 行是获得最多奖金的学生的姓名。 第 2 行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。 第 3 行是这 N 个学生获得的奖学金的总数。 样例： 123454YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1 123ChenRuiyi900028700 思路： 构造student结构体，包含编号num、姓名name、期末平均成绩avg、班级评议成绩cla_avg、学生干部position、西部身份west、论文数量paper、奖学金money 进行学生信息的录入，并通过func()函数计算某个学生的奖学金money 利用sort函 ...

奖学金 原题链接：http://oj.haizeix.com/problem/375 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。 期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。 输入： 共 n + 1 行。 第 1 行为一个正整数 n（6 ≤ n ≤ 300），表示该校参加评选的学生人数。 第 2 到 n + 1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 n − 1（恰好是输入数据的行号减 1）。 输出： 共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。 样例： 123456789880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 123458 2652 2646 2641 2585 258 思路： 构造student自定义类型，包含学生学号num、语文成绩chinese、数学成绩math、英语成绩english、总分all 进行学生信息的录入，并计算学生的总成绩 利用sort函数对student自定义类型按照给定的排序方式进行排序后进行输出 12345678910111213141516171819202122232425262728293031323334353637#include<iostream>#include<algorithm>using namespace std;//1.构造student自定义类型，包含学生所有信息struct student{ int num, chinese, math, english, all;};student stu[305];bool cmp(const student &a, const student &b){ if(a.all == b.all) ...

吃瓜群众 原题链接：http://oj.haizeix.com/problem/386 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M 堆瓜中查找对应数量的一堆瓜，并输出那堆瓜的编号，若找不到对应数量的一堆，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为对应数量的瓜的编号，若没有对应数量的瓜，则输出 0。 样例： 1235 31 3 26 7 1526 99 3 123302 1.参考解答思路1：暴力查找，每一组群众都对瓜堆进行遍历，时间复杂度为O(n^2)必超时 思路2： 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 利用sort函数对node自定义类型按照瓜的数量num进行排序 二分查找在瓜堆中查找，如果找到输出瓜堆数量num，否则输出0 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<iostream>#include<algorithm>#include<cstring>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cnt < b.cnt;}int main(){ int n, m; //2.进行瓜堆信息的录入 scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i)& ...

吃瓜群总升级版 原题链接：http://oj.haizeix.com/problem/387 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M堆瓜中查找大于等于需要数量的第一堆瓜，并输出那堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为大于等于需要数量的第一堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 样例： 1235 51 3 26 7 1527 10 3 4 2 1234505242 1.思路分析二分查找特殊情况的探讨01： 二分查找特殊情况的探讨10： 2.参考解答 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 若所有瓜堆的数量均小于需要数量输出0，否则输出大于等于需要数量的第一堆瓜的编号 方法1：建立一个最大虚拟瓜堆并将瓜堆数量置为0，当正常瓜堆中没有瓜堆满足条件时输出虚拟瓜堆数量 方法2：用最大的瓜堆的瓜数量判断，如果最大瓜堆数量大于需求则有答案进行二分，否则直接输出0 利用sort函数对node自定义类型按照瓜的数量num进行排序 利用二分查找在瓜堆中查找，如果找到输出瓜堆数量num 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<algorithm>#include<cstdio>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cn ...