杨校老师课堂之基于C++的sort排序与字符串解题_信息学奥赛-基础练习题

杨校

发布于 2025-02-23 07:56:41

14100

代码可运行

文章被收录于专栏：C++信息学奥赛C++信息学奥赛 Java技术分享圈

运行总次数：0

代码可运行

sort

sort()函数

sort()是实现排序的函数，它的作用类似于我们学习的冒泡排序和选择排序，可以对多个数据进行排序

sort()函数的基本格式

sort(首元素地址，尾元素地址的下一个地址);

默认从小到大排序

使用时必须添加头文件
#include

举个栗子:

(1)如果从a[0]开始存储
- sort(a,a+n); // 对a[0]~a[n-1]进行排序，

a[0]开始的n个元素

(2)如果从a[1]开始存储
- sort(a+1,a+n+1); // 对a[1]~a[n]进行排序，

a[0]开始的n个元素

string

函数名称	参数说明	函数用途
size()	无参	获取字符串的长度
length()	无参	获取字符串的长度
insert(pos, str)	pos为要插入的位置（从 0 开始计数），str为要插入的子串	指定位置插入子串
insert(pos, n,c)	pos为要插入的位置（从 0 开始计数），n为要插入字符c的个数，c为要插入的字符
replace(pos, len, str)	pos为开始替换的位置，len为要替换的字符个数，str为用于替换的子串	替换指定位置和长度的子串为新的子串
erase(pos, len)	pos为开始删除的位置，len为要删除的字符个数	删除指定位置和长度的子串
find(str, pos)	str为要查找的子串，pos为开始查找的位置（默认为 0）	从指定位置开始从左向右查找某个子串，找到则返回首次出现的位置，未找到返回string::npos
rfind(str, pos)	str为要查找的子串，pos为开始查找的位置（默认为字符串末尾）	从指定位置开始从右向左查找某个子串，找到则返回首次出现的位置，未找到返回string::npos
substr(pos, len)	pos为起始位置，len为子串长度（可选，默认为从pos到字符串末尾）	截取从指定位置开始的指定长度的子串
begin()	无参	从返回一个指向字符串首字符的迭代器，用于遍历字符串等操作
end()	无参	返回一个指向字符串尾字符的迭代器，用于遍历字符串等操作
compare()	str为要比较的字符串；或compare(pos, len, str)：pos为开始比较的位置，len为比较的长度，str为要比较的字符串；还有其他重载形式	比较两个字符串的大小关系，根据比较结果返回不同的值（如等于返回 0，大于返回正数，小于返回负数）
append(str)	str为要追加的字符串；还有其他重载形式，如可追加字符、追加指定数量的字符等	在字符串末尾追加子串
swap(str)	str为要交换的另一个字符串	交换两个字符串的内容
stoi(str, pos, base)	str为要转换的字符串，pos为一个整数指针，用于存储转换后字符串中第一个未转换字符的位置（可选），base为进制（可选，默认为 10）	将字符串转换为整型（int）
stol(str, pos, base)	str为要转换的字符串，pos为一个整数指针，用于存储转换后字符串中第一个未转换字符的位置（可选），base为进制（可选，默认为 10）	将字符串转换为整型（long）
stod(str, pos, base)	str为要转换的字符串，pos为一个整数指针，用于存储转换后字符串中第一个未转换字符的位置（可选），base为进制（可选，默认为 10）	将字符串转换为浮点型（double）
to_string(value)	value为要转换为字符串的数值（整型、浮点型等）	将数值转换为字符串

1. 记忆之王

题目描述陈平安参加了Coduck王国举办的记忆之王比赛，比赛规则是给出一篇文章，让所有选手以最快的速度进行记忆，记忆时间最短的三名选手依次获得记忆之王、记忆强者、记忆达人的称号，本次比赛一共有n名选手参赛，请根据他们的的记忆时间，选出其中最短的三个时间按从小到大的顺序输出。

输入描述输入2行，

第一行一个整数n表示参赛人数(1<=n<=10000)

第二行n个整数代表每位选手的记忆时间t(1<=t<=1000)

输出描述三行，分别为记忆时间最短的三名选手的记忆用时。

样例输入

5 15 89 72 34 48

输出

15 34 48

参考答案

解法不唯一

#include <iostream>
#include <algorithm>
using namespace std;

int a[10005];
int main(){
// 定义 
  int n;
  cin >> n;
//   输入
  for (int i = 0; i < n; i++) {
      cin >> a[i];
  }
//   梳理，对数组进行排序
  sort(a,a+n);
//   输出前三
  for (int i = 0; i < 3; i++) {
      cout << a[i] <<endl;
  }
  
  return 0;
}

2. 字符排序

题目描述： 任意输入一个长度不超过20的字符串，对所输入的字符串，按照ASCII码的大小从小到大进行排序，请输出排序后的结果。

输入描述 输入第一行为样例数m，接下来m行每行一个字符串，字符串长度不超过20。

输出描述 输出m行表示排序完的字符串。

样例输入

1 dcab

输出

abcd

参考答案

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


int main(){
// 定义 
  int m;string str;
//   输入
  cin >> m;
//  循环处理
  while(m--){
      cin >> str;
      //   处理，对字符串排序，起始位置
      sort(str.begin(),str.end());
      //  输出
      cout << str << endl;
  }
  


  return 0;
}

3. 列国纷争

题目描述 在一次十国会议上，需要对各个国家进行排名统计，各国代表都吵着要排在靠前的位置，这时候龙国代表提出一个解决方案得到了所有人的认同。这个方案就是，将国家的名字按照字母大小来排序。请你写一个程序来实现本次排序。

输入描述 10行，每行一个国家名，国家名可能存在空格。(长度不超过100)

输出描述 10行，每行一个国家名，按字母顺序排列。

样例输入

Japan Lithuania Albania South Africa Romania Thailand Mexico Korea France China

输出

Albania China France Japan Korea Lithuania Mexico Romania South Africa Thailand

参考答案

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


int main(){
// 定义 
    string str[15];
    // 循环输入
    for (int i = 0; i < 10; i++) {
        //   输入        
        getline(cin,str[i]);
    }
    
    sort(str,str+10);

    for (int i = 0; i < 10; i++) {
        cout << str[i] << endl;
    }
    return 0;
}

4. 姓名排序

输入描述输入第一行为样例数m，对于每个样例，第一行为人数n，接下来有n个姓名,n不超过10，每个名字长度不超过20。

输出描述对于每个样例输出排序后的结果，每行一个姓名。

样例输入

1 4 Apple Tom Green Jack

输出

Apple Green Jack Tom

参考答案

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int n,m;
    string str[15];
    cin >> m;
   while(m--){
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> str[i];
        }
        sort(str,str+n);
        for (int i = 0; i < n; i++) {
            cout << str[i] << endl;
        }
   }
    
    return 0;
}

5. 跳绳比赛

题目描述 巅峰小学举行1分钟跳绳比赛，n人一组。试编一程序，输入小组内同学的跳绳次数，按次数由多到少的顺序输出。

输入描述 第1行为 n。n≤100。第2行为 n 个正整数，其间用空格间隔。

输出描述 一行，由多到少的排序的结果。

样例输入

5 126 80 98 158 204

输出

204 158 126 98 80

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int a[105];
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a,a+n,cmp);
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    return 0;
}

6. 谁是第N名

题目描述 考试结束后,同学们的成绩都不一样,知道了学生的考号以及分数,找出谁是第N名。

输入描述 第一行有两个整数，分别是学生的人数m（1≤m≤100），和求第N名学生的（1≤N≤m）。其后有m行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。

输出描述 输出第N名学生的学号和成绩，中间用空格分隔。

样例输入

5 3 90788001 67.8 90788002 90.3 90788003 61 90788004 68.4 90788005 73.9

输出

90788004 68.4

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct stu{
  int sid;
  double score;
}a[105];

bool cmp(stu a,stu b){
    return a.score>b.score;
}
int main(){
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i].sid >> a[i].score;
    }
    sort(a,a+n,cmp);
     cout << a[m-1].sid << ' ' << a[m-1].score << endl;
    return 0;
}

7. 排名

题目描述 一年一度的江苏省小学生程序设计比赛开始了，组委会公布了所有学生的成绩，成绩按分数从高到低排名，成绩相同按年级从低到高排名。现在主办单位想知道每一个排名的学生前，有几位学生的年级低于他。

输入描述 第一行只有一个正整数n（1<=n<=200),表示参数的学生人数

第2~n+1行，每行有两个正整数s（0<=s<=400)和g(1<=g<=6),之间用一个空格隔开，其中第i+1行的第一个数s表示第i个学生的成绩，第i+1行的第二个数g表示第i个学生的年级

输出描述 输出n行，每行只有一个正整数，其中第i行的数k表示排第i名的学生前面有k个学生排名比他高，且年级比他低

样例输入

5 300 5 200 6 350 4 400 6 250 5

输出

0 0 1 1 3

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct stu{
    // 成绩、年级
  int score,grade;
}a[205];

bool cmp(stu a,stu b){
  if(a.score == b.score){
        return a.grade<b.grade;
  }
    return a.score>b.score;
}
int main(){
    int n;
    cin >> n ;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].score >> a[i].grade;
    }
    sort(a+1,a+n+1,cmp);
    for (int i = 1; i <= n; i++) {
      int cnt = 0;
      for (int j = 1; j <= i; j++) {
        if(a[i].grade > a[j].grade){
           cnt++;
        }
      }
        cout << cnt << endl;
    }
    return 0;
}

对于每个学生（循环i从 1 到n），重新计算cnt。通过内层循环（j从 1 到i - 1），检查前面的学生（排名比当前学生高）中年级比当前学生低的数量，符合条件就增加cnt。最后输出cnt，即排第i名的学生前面有cnt个学生排名比他高且年级比他低。

8. 分数线是多少

题目描述 剑气长城如火如荼地进行了编程比赛，通过二轮测试的同学将会得到丰厚的礼品，首先根据一轮测试的结果划定一个分数线，分数线根据最终得奖人数的150%划定，即如果计划最终得奖人数为m名，则分数线为排名第m*150%（向下取整）名的选手的分数。请你划定一下这个编程比赛的分数线，输出可以有机会得到礼品的同学的报名号和成绩。

输入描述 第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加一轮测试的学生总数，m 表示最终得奖人数。输入数据保证m*150%向下取整后小于等于n。

第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是学生的报名号k（1000 ≤ k ≤ 9999）和该学生的一轮测试成绩s（1 ≤ s ≤ 100）。数据保证学生的报名号各不相同.

输出描述 第一行，有两个整数，用一个空格隔开，第一个整数表示进入二轮测试的分数线；第二个整数为进入二轮测试的学生实际人数

从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入二轮测试的学的的报名号和一轮测试成绩，按照成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例输入

6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88

输出

88 5 1005 95 2390 95 1000 90 1001 88 3239 88

参考答案

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct stu{
    // 报名号k、测试成绩s
  int k,s;
}a[5005];

bool cmp(stu a,stu b){
    if(a.s==b.s){
        return a.k<b.k;
    }
    return a.s>b.s;
}
int main(){
    int n,m,cnt=0;
    cin >> n >> m ;
    m = m * 1.5;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].k >> a[i].s;
    }
    sort(a+1,a+n+1,cmp);
    // cout << a[m].s<< endl; //  进入二轮测试的分数线
    for (int i = 1; i <= n; i++){
        // cout <<  a[i].k << " "<< a[i].s << endl;
        if(a[i].s >= a[m].s){
            cnt++;
        }
    }
    cout << a[m].s << " "<<cnt << endl;
     for (int i = 1; i <= cnt; i++){
        cout <<  a[i].k << " "<< a[i].s << endl;
       
    }
    return 0;
}

9. 迷糊的陈平安

题目描述 陈平安总是爱犯糊涂，这不他又开始晕乎了~如果给他一个句子（一行），他会将句子中的每一个单词翻转后输出。那么用计算机是如何实现的呢？

输入描述 只有一行，为一个字符串，不超过500个字符。单词之间以空格隔开。

输出描述 翻转每一个单词后的字符串，单词之间的空格需与原文一致。

样例输入

hello world

输出

olleh dlrow

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;


int main(){
    string str,str1,str2;
    getline(cin,str);
    if(str.find(" ")!= -1){
        str1 = str.substr(0,str.find(" "));
        str2 = str.substr(str.find(" "));
        reverse(str1.begin(),str1.end());
        reverse(str2.begin(),str2.end());
        str = str1 + " " + str2;
        cout << str;
    }else{
       reverse(str.begin(),str.end());
       cout << str;
    }
   
  
    
    return 0;
}

10. 字符合并

题目描述 现有2行字符串，要求我们把两行字符串合并，合并规则如下： 1.第一个字符串的长度为偶数； 2.把第2个字符串插入到第一个串的正中央。

输入描述 输入数据首先给出一个整数n，表示测试数据的组数。n≤3000。然后是n组数据，每组数据2行，每行一个字符串，长度大于0，小于50，并且第一个串的长度必为偶数。

输出描述 每组数据输出一行，表示合并操作之后的字符串。

样例输入

2 CSJI BI AB CMCLU

输出

CSBIJI ACMCLUB

#include <iostream>
#include <string>



using namespace std;

int main(){
    int n ;string str,str1,str2;
    cin >> n;
    while(n--){
        cin >> str;
        cin >> str1;
        int len = str.size()/2;
        str2 = str.insert(len,str1);
    
        cout << str2 << endl;
    }
    return 0;
}

11. 文字处理软件

题目描述 你需要开发一款文字处理软件。最开始时输入一个字符串（不超过 100 个字符）作为初始文档。可以认为文档开头是第 0 个字符。需要支持以下操作： • 1 str：后接插入，在文档后面插入字符串 str，并输出文档的字符串。 • 2 a b：截取文档部分，只保留文档中从第 a 个字符起 b 个字符，并输出文档的字符串。 • 3 a str：插入片段，在文档中第 a 个字符前面插入字符串 str，并输出文档的字符串。 • 4 str：查找子串，查找字符串 str 在文档中最先的位置并输出；如果找不到输出 -1。为了简化问题，规定初始的文档和每次操作中的 str 都不含有空格或换行。最多会有q(q≤100) 次操作。。

输入描述

输出描述

样例输入

4 ILove 1 Coduck 2 5 5 3 3 duckDuckduck 4 duck

输出

ILoveCoduck Coduc CodduckDuckduckuc 3

#include <iostream>
#include <string>



using namespace std;

int main(){
    int q,cmd,a,b ;string str,str1,str2;
    cin >> q;
    cin >> str;
    while(q--){
        
        cin>> cmd ;
       switch(cmd){
           case 1:
           cin >> str1;
            str.append(str1);
            cout << str << endl;
           break;
            case 2:
            cin>> a >> b;
            str1 = str.substr(a,b);
            str = str1;
            cout << str1 << endl;
           break;
            case 3:
             cin>> a >> str2;
            str.insert(a,str2);
            cout << str << endl;
           break;
            case 4:
             cin>> str1;
            int pos = str.find(str1);
            cout << pos << endl;
           break;
           
       }
    }
    return 0;
}

12. 行程长度编码

题目描述 在数据压缩中，一个常用的途径是行程长度压缩。对于一个待压缩的字符串而言，我们可以依次记录每个字符及重复的次数。这种压缩，对于相邻数据重复较多的情况比较有效。例如，如果待压缩串为"AAABBBBCBB"，则压缩的结果是(A,3)(B,4)(C,1)(B,2)。当然，如果相邻字符重复情况较少，则压缩效率就较低。

现要求根据输入的字符串，得到大小写不敏感压缩后的结果（即所有小写字母均视为相应的大写字母）。

输入描述 一个字符串，长度大于0，且不超过1000，全部由大写或小写字母组成。

输出描述 输出为一行，表示压缩结果，形式为： (A,3)(B,4)(C,1)(B,2) 即每对括号内部分别为字符（都为大写）及重复出现的次数，不含任何空格。

样例输入

aAABBbBCCCaaaaa

输出

(A,3)(B,4)(C,3)(A,5)

#include <iostream>
#include <string>
#include <cstring>
#include <cctype>

using namespace std;

int main(){
    string str ,str1;
    int cnt = 0;
    cin >> str;
  
    for (int i = 0; i <str.size() ; i++) {
       str1 +=  toupper(str[i]);
    }
    int len= str1.size();
    char curStr = str1[0];
    for (int i = 1; i <= len; i++) {
     
        if(i==str1.size() || curStr != str1[i]){
            cout << "(" <<  str1[i] << cnt <<  ")";
            if(i<str1.size()){
                curStr = str1[i];
                cnt = 1;
            }
        }else{
            cnt++;
        }
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-29，如有侵权请联系 cloudcommunity@tencent.com 删除

sort