ACM程序设计课内实验（2） 排序问题

2023-12-01 02:12
文章标签 问题 排序 实验 程序设计 acm 课内

本文主要是介绍ACM程序设计课内实验（2） 排序问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基础知识‘

sort函数

C++中的sort函数是库中的一个函数，用于对容器中的元素进行排序。它的原型如下：

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

参数说明：
  • first：指向要排序序列的第一个元素的迭代器。
  • last：指向要排序序列的最后一个元素的下一个位置的迭代器。
  • comp：一个比较函数，用于指定排序的顺序。默认情况下，它使用operator<进行升序排序。如果需要降序排序，可以提供一个自定义的比较函数。

qsort函数

C++中的qsort函数是一个通用的排序函数，它位于头文件中。qsort函数接受一个数组、数组的大小以及一个比较函数作为参数。比较函数用于确定数组中元素的顺序。

#include <cstdlib>
#include <iostream>
#include <algorithm>using namespace std;//定义比较函数，用于排序
int cmp(const void *a, const void *b)
{int *pa=(int *)a;int *pb=(int *)b;return *pa-*pb;
}int main()
{int arr[]={10, 8, 2, 6, 7, 3};int len=sizeof(arr)/sizeof(arr[0]);qsort(arr, len, sizeof(int), cmp);for(int i=0;i<len;i++){cout<<arr[i]<<" ";}return 0;
}

 1.排序

Description

给你很多行数，将每行数排序（从小到大）！

Input

输入数据有很多行，每行10个正整数。

Output

将每行数从小到大输出。

Sample Input

10 9 8 7 6 5 4 3 2 1

Sample Output

1 2 3 4 5 6 7 8 9 10

#include <iostream>
#include <sstream>
#include <algorithm>using namespace std;// 快速排序函数，arr为待排序数组，left为左边界，right为右边界
void quickSort(int arr[], int left, int right) {if (left < right) {int pivot = arr[left]; // 选择基准值int i = left; // 左指针int j = right; // 右指针while (i < j) {// 从右向左找到第一个小于基准值的元素while (i < j && arr[j] >= pivot) {j--;}// 如果找到了，将其与左指针指向的元素交换，并将左指针向右移动一位if (i < j) {arr[i++] = arr[j];}// 从左向右找到第一个大于基准值的元素while (i < j && arr[i] < pivot) {i++;}// 如果找到了，将其与右指针指向的元素交换，并将右指针向左移动一位if (i < j) {arr[j--] = arr[i];}}// 将基准值放到正确的位置上arr[i] = pivot;// 递归地对左右两部分进行快速排序quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}
}int main() {int arr[100];while(scanf("%d",&arr[0])!=EOF){ for(int i=1; i<10; i++) scanf("%d",&arr[i]);quickSort(arr, 0, 9);for (int i = 0; i < 10; i++) { cout << arr[i] << " ";}cout << endl; }return 0;
}

 2.枫之舞------排序

Description

你会排序吗？请将给出的数据按（升序）排序~~

Input

输入数据有多组，首先输入一个T，代表有T组数，然后是T行，每行开头是N,代表有N个数需要排序，然后就是这N个要排序的数了！N大于1且小于1000.

Output

把数据从小到大排序。

Sample Input

2
3 2 1 3
9 1 4 7 2 5 8 3 6 9

Sample Output

1 2 3
1 2 3 4 5 6 7 8 9
#include <bits/stdc++.h>
using namespace std;
int x[1005];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;for(int i=0;i<n;i++)scanf("%d",&x[i]);sort(x,x+n,less<int>());for(int i=0;i<n-1;i++)printf("%d ",x[i]);printf("%d",x[n-1]);printf("\n");}return 0;
}

 3.让气球飞吧

Description

国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛，ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成，一个队每做出来一个题该队就会获得该题对应颜色的气球，气球越多就说明该队做的题目越多。当然如果一个颜色的气球越多就说明该气球对应的题也就越简单。现在给你很多很多的颜色的气球，问你那个颜色的气球最多，哈哈，聪明的acmer这题对你肯定很简单吧， just ac it！

Input

假设只有6种颜色，green，red，blue，pink，orange，black。输入数据有多组，每组数据开始给出一个整数n代表接下来有n个气球，接下来有n行，每行输入一种颜色，n <= 100,输入以EOF结束。

Output

输出个数最多的气球的颜色（题目保证个数最多的气球有且仅有一种颜色）

Sample Input

3
green
red
green
5
green
red
blue
red
red

Sample Output

green
red

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{char b[6][10]= {"red","green","blue","pink","black","orange"};int n;while(scanf("%d",&n)!=EOF){int res[6]= {0};int k;for(k=0; k<n; k++){char a[10];scanf("%s",a);int i;for(i=0; i<6; i++){if(strcmp(b[i],a)==0)res[i]++;}}int num=0,max=res[0];int j;for(j=1; j<6; j++){if(max<res[j]){max=res[j];num=j;}}printf("%s\n",b[num]);}return 0;
}

改进

#include <iostream>
#include <map>
#include <string>
using namespace std;int main() {int n;string color;map<string, int> color_count;while (scanf("%d",&n)!=EOF) {color_count.clear();for (int i = 0; i < n; i++) {cin>>color;color_count[color]++;}string max_color = "";int max_count = 0;for (const auto &p : color_count) {if (p.second > max_count) {max_count = p.second;max_color = p.first;}}cout << max_color << endl;}return 0;
}

4.Google is Feeling Lucky

描述

        谷歌是最著名的互联网搜索引擎之一，它托管和开发了许多基于互联网的服务和产品。在其搜索引擎网站上，一个有趣的按钮“我感觉很幸运”吸引了我们的眼球。该功能可以允许用户跳过搜索结果页面，直接进入排名第一的页面。


        太神了它节省了很多时间。


        问题是，当一个人键入一些关键词并按下“我感觉很幸运”按钮时，会出现哪个网页？谷歌做了很多工作，并提出了很好的方法来处理它。在这个简化的问题中，让我们只考虑谷歌为每个网页分配一个整数值的相关性。将选择最相关的页面。如果出现平局，则可以选择相关性最高的所有页面。


        你的任务很简单，给定10个网页及其相关性。只要挑选出所有可能的候选人，当“我感到幸运”时就会提供给用户。

输入

输入包含多个测试用例。测试用例的数量T在输入文件的第一行中。
对于每个测试用例，有10行描述网页和相关性。每一行都包含一个字符串，没有任何空白字符表示该网页的URL，以及一个整数Vi表示该网页相关性。URL的长度介于1和100之间（包括1和100）。（1<=Vi<=100）

输出

对于每个测试用例，输出几行，这些行是可以选择的网页的URL。URL的顺序与输入的顺序相同。
有关输出格式的更多信息，请查看示例输出。

样本输入

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10


www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10


样本输出

案例1：
www.alibaba.com
www.bad.com
acm.university.edu.cn
案例2：
www.alibaba.com

方法一

#include <bits/stdc++.h>
using namespace std;
int main()
{int t;cin>>t;int n=1;while(t--){char ch[12][120];int num[12];for(int i=1; i<=10; i++)cin>>ch[i]>>num[i];int maxn=-999999;for(int i=1; i<=10; i++){if(num[i]>maxn)maxn=num[i];}printf("Case #%d:\n",n);n++;for(int i=1; i<=10; i++)if(num[i]==maxn)cout<<ch[i]<<endl;}return 0;
}

 方法二

#include <iostream>
#include <algorithm>
#include <string>using namespace std;struct WebPage {string url;int relevance;
};bool compare(const WebPage &a, const WebPage &b) {if (a.relevance == b.relevance) {return a.url < b.url;}return a.relevance > b.relevance;
}int main() {int T;cin >> T;for (int t = 0; t < T; ++t) {WebPage webPages[10];for (int i = 0; i < 10; ++i) {cin >> webPages[i].url >> webPages[i].relevance;}sort(webPages, webPages + 10, compare);cout << "Case #" << t + 1 << ":" << endl;cout << webPages[0].url << endl;for (int i = 1; i < 10; ++i) {if(webPages[i].relevance == webPages[0].relevance)cout << webPages[i].url << endl;}cout << endl;}return 0;
}

5.数字排序

Description

现在给出一个不超过1000个数字（允许重复），小新想知道其中的数字
是第几小的数,例如给出5 4 4 2 1，1就是第一小的数，4就是第3小的数，5
就是滴小的数。

Input

多组样例。每组第一行是一个整数n,跟着n(n <= 1000)个整数(a1,a2,a3,……，an)，
第二行一个整数m( m < 100)表示将要询问的次数，跟着m个整数（b1,b2,b3……，bn）

Output

对于每次询问输出一行，表示bi(i >= 1&& i <= m)是第几小的数，如果aj(j >= 1 && j <= n)中
不存在bj则直接输出-1.

Sample Input

5 5 4 4 2 1
3 1 4 5
3 1 3 2
3 1 4 2

Sample Output

1
3
4
1
-1
2
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
set<int> vis;
set<int>::iterator it;
int main()
{int i,j,m,n,flag,k;while(cin>>n){vis.clear();for(i=1;i<=n;i++){cin>>m;vis.insert(m);}cin>>m;int p;for(i=1;i<=m;i++){flag=-1;cin>>p;for(it=vis.begin(),k=1;it!=vis.end();it++,k++){if(p==*it){flag=k;break;}}cout<<flag<<endl;}}return 0;
}

 

这篇关于ACM程序设计课内实验（2） 排序问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/439415。

相关文章

IDEA和GIT关于文件中LF和CRLF问题及解决

IDEA和GIT关于文件中LF和CRLF问题及解决

《IDEA和GIT关于文件中LF和CRLF问题及解决》文章总结：因IDEA默认使用CRLF换行符导致Shell脚本在Linux运行报错,需在编辑器和Git中统一为LF,通过调整Git的core.aut... 目录问题描述问题思考解决过程总结问题描述项目软件安装shell脚本上git仓库管理，但拉取后，上l
阅读更多...
idea npm install很慢问题及解决(nodejs)

idea npm install很慢问题及解决(nodejs)

《ideanpminstall很慢问题及解决(nodejs)》npm安装速度慢可通过配置国内镜像源（如淘宝）、清理缓存及切换工具解决,建议设置全局镜像（npmconfigsetregistryht... 目录idea npm install很慢(nodejs)配置国内镜像源清理缓存总结idea npm in
阅读更多...
pycharm跑python项目易出错的问题总结

pycharm跑python项目易出错的问题总结

《pycharm跑python项目易出错的问题总结》：本文主要介绍pycharm跑python项目易出错问题的相关资料,当你在PyCharm中运行Python程序时遇到报错,可以按照以下步骤进行排... 1. 一定不要在pycharm终端里面创建环境安装别人的项目子模块等，有可能出现的问题就是你不报错都安装
阅读更多...
idea突然报错Malformed \uxxxx encoding问题及解决

idea突然报错Malformed \uxxxx encoding问题及解决

《idea突然报错Malformeduxxxxencoding问题及解决》Maven项目在切换Git分支时报错,提示project元素为描述符根元素,解决方法：删除Maven仓库中的resolv... 目www.chinasem.cn录问题解决方式总结问题idea 上的 maven China编程项目突然报错，是
阅读更多...
Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

《Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题》在爬虫工程里,“HTTPS”是绕不开的话题,HTTPS为传输加密提供保护,同时也给爬虫带来证书校验、... 目录一、核心问题与优先级检查（先问三件事）二、基础示例：requests 与证书处理三、高并发选型：
阅读更多...
前端导出Excel文件出现乱码或文件损坏问题的解决办法

前端导出Excel文件出现乱码或文件损坏问题的解决办法

《前端导出Excel文件出现乱码或文件损坏问题的解决办法》在现代网页应用程序中,前端有时需要与后端进行数据交互,包括下载文件,：本文主要介绍前端导出Excel文件出现乱码或文件损坏问题的解决办法,... 目录1. 检查后端返回的数据格式2. 前端正确处理二进制数据方案 1：直接下载（推荐）方案 2：手动构造
阅读更多...
Python绘制TSP、VRP问题求解结果图全过程

Python绘制TSP、VRP问题求解结果图全过程

《Python绘制TSP、VRP问题求解结果图全过程》本文介绍用Python绘制TSP和VRP问题的静态与动态结果图,静态图展示路径,动态图通过matplotlib.animation模块实现动画效果... 目录一、静态图二、动态图总结【代码】python绘制TSP、VRP问题求解结果图（包含静态图与动态图
阅读更多...
MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

《MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决》MyBatis默认开启一级缓存,同一事务中循环调用查询方法时会重复使用缓存数据,导致获取的序列主键值均为1,... 目录问题原因解决办法如果是存储过程总结问题myBATis有如下代码获取序列作为主键IdMappe
阅读更多...
k8s容器放开锁内存限制问题

k8s容器放开锁内存限制问题

《k8s容器放开锁内存限制问题》nccl-test容器运行mpirun时因NCCL_BUFFSIZE过大导致OOM,需通过修改docker服务配置文件,将LimitMEMLOCK设为infinity并... 目录问题问题确认放开容器max locked memory限制总结参考：https://Access
阅读更多...
Java中字符编码问题的解决方法详解

Java中字符编码问题的解决方法详解

《Java中字符编码问题的解决方法详解》在日常Java开发中,字符编码问题是一个非常常见却又特别容易踩坑的地方,这篇文章就带你一步一步看清楚字符编码的来龙去脉,并结合可运行的代码,看看如何在Java项... 目录前言背景：为什么会出现编码问题常见场景分析控制台输出乱码文件读写乱码数据库存取乱码解决方案统一使
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2