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。

相关文章

mybatis和mybatis-plus设置值为null不起作用问题及解决

mybatis和mybatis-plus设置值为null不起作用问题及解决

《mybatis和mybatis-plus设置值为null不起作用问题及解决》Mybatis-Plus的FieldStrategy主要用于控制新增、更新和查询时对空值的处理策略,通过配置不同的策略类型... 目录MyBATis-plusFieldStrategy作用FieldStrategy类型每种策略的作
阅读更多...
linux下多个硬盘划分到同一挂载点问题

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理（LVM）来实现,首先,需要将物理存储设备（如硬盘分区）创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多
阅读更多...
Python Jupyter Notebook导包报错问题及解决

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了
阅读更多...
pip install jupyterlab失败的原因问题及探索

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型，然后其中要下载jupyter(有点LSVmu像一个
阅读更多...
解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

《解决jupyterLab打开后出现Configoption`template_path`notrecognizedby`ExporterCollapsibleHeadings`问题》在Ju... 目录jupyterLab打开后出现“templandroidate_path”相关问题这是 tensorflo
阅读更多...
如何解决Pycharm编辑内容时有光标的问题

如何解决Pycharm编辑内容时有光标的问题

《如何解决Pycharm编辑内容时有光标的问题》文章介绍了如何在PyCharm中配置VimEmulator插件,包括检查插件是否已安装、下载插件以及安装IdeaVim插件的步骤... 目录Pycharm编辑内容时有光标1.如果Vim Emulator前面有对勾2.www.chinasem.cn如果tools工
阅读更多...
最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
Java多线程父线程向子线程传值问题及解决

Java多线程父线程向子线程传值问题及解决

《Java多线程父线程向子线程传值问题及解决》文章总结了5种解决父子之间数据传递困扰的解决方案,包括ThreadLocal+TaskDecorator、UserUtils、CustomTaskDeco... 目录1 背景2 ThreadLocal+TaskDecorator3 RequestContextH
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
关于最长递增子序列问题概述

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法：贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列，例如 nums = [10, 9, 2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2