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

于 2024-12-29 12:03:41 发布
阅读量1k 收藏 18
点赞数 22
文章标签： c++ java 算法
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/kese7952/article/details/144689263
版权

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;
}
钽电容封装大全及技术参数.doc
05-05
钽电容封装大全及技术参数
钽电容PCB封装
02-24
钽电容的PCB封装，AD14,SMD-CT-2010,3216,3528,6032,7343
贴片钽电容封封装及规格和参数资料
小丁BLOG
12-19 4610
贴片钽电容（以下简称钽电容）作为电解电容器中的一类。广泛应用于各类电子产品，特别是一些高密度组装，内部空间体积小产品，如手机、便携式打印机 。 钽电容是一种用金属钽（Ta）作为阳极材料而制成的，按阳极结构的不同可分为箔式和钽烧粉结式两种。在钽粉烧结式钽电容中，又因工作电解质不同，分为固体电解质钽电容（Solid Tantalum）和非固体电解质钽电容。 其中，固体钽电解电容器用量最大。钽电容由
贴片钽电容封装尺寸表
weixin_34372728的博客
01-01 1928
知道贴片钽电容的容量和耐压值即可查询到相应的封装尺寸，同时您也可以在本文里找到贴片钽电容有哪些容量和耐压等级。 第一步：确定您所选择的贴片钽电容容量和耐压值 　　常用贴片钽电容的容量范围和耐压范围见表1。其中“代码”列代表贴片钽电容容量标注代码，白色背景表格里的英文字母（A、B、C、D等）为尺寸代码（用蓝色标注的尺寸代码为非常规封装尺寸，选择型时应优先选择黑色标注的尺寸），...
钽电容封装
wo0007的博客
09-11 1167
钽电容封装
钽电容各种容值封装尺寸详解
09-04
钽电容具体的封装大小及容值介绍，包括A，B，C，D，E，V型及各种容值大小对应何种类型
贴片钽电容封装及规格参数资料
的博客
10-28 6544
注意，为防止电容烧毁，一般钽电容使用电压为电路工作电压的两倍 　　贴片钽电容（以下简称钽电容）作为电解电容器中的一类。广泛应用于各类电子产品，特别是一些高密度组装，内部空间体积小产品，如手机、便携式打印机 。 钽电容是一种用金属钽（Ta）作为阳极材料而制成的，按阳极结构的不同可分为箔式和钽烧粉结式两种。在钽粉烧结式钽电容中，又因工作电解质不同，分为固体电解质钽电容（Solid Tantalum）和非固体电解质钽电容。 其中，固体钽电解电容器用量最大。钽电容由于使用金属钽做介质，不需要像普通电解电容那样使用
常用电容封装，带3D，钽电容封装
04-26
电容封装，钽电容封装，0603封装，1206封装，3126封装，3528封装，6032封装，0805封装。。。。。电容封装，钽电容封装，0603封装，1206封装，3126封装，3528封装，6032封装，0805封装
钽电容规格标准
09-24
钽电容规格标准，钽电容介绍，钽电容技术规格和选型（以VISHAY 和AVX 为例说明）。
20130408-[转]贴片钽电容的封装、尺寸和标识
2974786048的专栏
04-08 2108
贴片钽电容的封装、尺寸 Code EIA Code L±0.20 (0.008) W+0.20 (0.008) -0.10 (0.004) H+0.20 (0.008) -0.10 (0.004) W1±0.20 (0.008) A+0.30 (0.012) -0.20 (0.008) S Min. A 3216-18 3.20 (
【标准化封装 钽电容封装】Tantalum Capacitors 各种壳
最新发布
hcoolabc的博客
11-01 870
钽电容你见到的是什么封装？7343？那是D壳还是E壳？有没有PCB焊接调试好，结构缺盖不住盖子了？？？
贴片钽电容封封装及规格和参数资料（转载）
10-06 1426
钽电容封装
钽电容选型与封装
tsliuch的专栏
01-14 3099
以下LVX钽电容选型资料（其它厂家也有类似产品，但参数可能存在不同） 长的话是+-0.2 ,宽是+-0.1 高 （MM） A 型的尺寸 3.2 X1.6 X1.6 俗称: A(3216) B 型的尺寸 3.5 X2.8 X1.9 俗称: B(3528) C 型的尺寸 6.0X 3.2X 2.6 俗称: C(6032) D 型的尺寸 7.3 X4.3 X2.9 俗称: D(7343) 厚度2.9英寸 E 型的尺寸 7.3 X4.3 X4.1 俗称: E(7343) 厚...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

杨校

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值