洛谷 【算法1-2】排序

【算法1-2】排序 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

鄙人不才，刷洛谷，迎蓝桥，【算法1-2】排序 已刷，现将 AC 代码献上，望有助于各位

P1271 选举学生会

【深基9.例1】选举学生会 - 洛谷

题目

解答

思路

将候选人编号及其获得的票数映射到一个一维数组上（即依据候选人编号对票数进行排序），然后根据获得的票数输出编号，如，a 号 获得 b 票，则输出 b 个 a

代码

#include<iostream>
using namespace std;
int ren[1005] = { 0 };
int n;
int m;
int main() {
	cin >> n >> m;
	int piao;
	for (int i = 1; i <= m; i++) {
		cin >> piao;
		ren[piao]++;
	}
	for (int i = 1; i <= n; i++) {
		if(ren[i]!=0)
			for (int j = 0; j < ren[i]; j++) {
				cout << i << " ";
			}
	}
	return 0;
}

P1177 排序

【模板】排序 - 洛谷

题目

解答

思路

快排和归并排序模板均可解决

代码

//快排
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100005];
void quick_sort(int a[], int l, int r) {
	if (l >= r)
		return;
	int base = a[l + r >> 1], i = l - 1, j = r + 1;
	while (i < j) {
		do i++; while (a[i] < base);
		do j--; while (a[j] > base);
		if (i < j)
			swap(a[i], a[j]);
	}
	quick_sort(a, l, j);
	quick_sort(a, j + 1, r);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	quick_sort(a, 0, n - 1);
	for (int i = 0; i < n - 1; i++)
		cout << a[i] << " ";
	cout << a[n - 1] << endl;
	return 0;
}

//归并排序
#include<iostream>
using namespace std;
int n;
int a[100005], tmp[100005];
void merge_sort(int a[], int l, int r) {
	if (l >= r)
		return;
	int mid = (l + r) / 2;
	merge_sort(a, l, mid);
	merge_sort(a, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (a[i] < a[j]) {
			tmp[k] = a[i];
			k++;
			i++;
		}
		else {
			tmp[k] = a[j];
			k++;
			j++;
		}
	}
	while (i <= mid) {
		tmp[k] = a[i];
		k++;
		i++;
	}
	while (j <= r) {
		tmp[k] = a[j];
		k++;
		j++;
	}
	for (int i = l, j = 0; i <= r; i++, j++)
		a[i] = tmp[j];
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	merge_sort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}

P1059 明明的随机数

[NOIP2006 普及组] 明明的随机数 - 洛谷

题目

解答

思路

使用数组映射产生的随机数，数组元素的下标表示产生的随机数，对应的数组元素表示该数的个数

代码

#include<iostream>
using namespace std;
int N;
int num[1005] = { 0 };
int a[105];
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		num[a[i]]++;
	}
	int q = 0;
	int b[100];
	for (int i = 1; i <= 1000; i++) {
		if (num[i] != 0) {
			b[q] = i;
			q++;
		}	
	}
	cout << q << endl;
	for (int i = 0; i < q; i++)
		cout << b[i] << " ";
	return 0;
}

P1923 求第 k 小的数

【深基9.例4】求第 k 小的数 - 洛谷

题目

解答

思路

使用 nth_element

当采用默认的升序排序规则时，nth_element()可以从某个序列中找到第 n 小的元素 K，并将 K 移动到序列中第 n 的位置，且整个序列经过此函数处理后，所有位于 K 之前的元素都比 K 小，所有位于 K 之后的元素都比 K 大

快排+二分

快排一次，将数组分为三个区间，分别是小于基准数、等于基准数、大于基准数三个部分，根据 k 与 i 和 j 的关系确定下一次递归的区间

代码

//使用nth_element()
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
int k;
const int N = 5e6 + 100;
int a[N];
int main() {
	scanf("%d%d",&n,&k);
	for (int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	nth_element(a, a + k, a + n);
	printf("%d",a[k]);
	return 0;
}

P1093 奖学金

[NOIP2007 普及组] 奖学金 - 洛谷

题目

解答

思路

写一个比较函数即可

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct student {
	int num;
	int ch;
	int ma;
	int eng;
	int sum = 0;
}student;
bool cmp(student s1, student s2) {
	if (s1.sum != s2.sum)
		return s1.sum > s2.sum;
	else {
		if (s1.ch != s2.ch)
			return s1.ch > s2.ch;
		else
			return s1.num < s2.num;
	}
}
int main() {
	int n;
	cin >> n;
	student stu[305];
	for (int i = 0; i < n; i++) {
		cin >> stu[i].ch;
		cin >> stu[i].ma;
		cin >> stu[i].eng;
		stu[i].num = i + 1;
		stu[i].sum = stu[i].ch + stu[i].ma + stu[i].eng;
	}
	sort(stu, stu + n, cmp);
	for (int i = 0; i < 5; i++) {
		cout << stu[i].num << " " << stu[i].sum << endl;
	}
	return 0;
}

P1781 宇宙总统

宇宙总统 - 洛谷

题目

解答

思路

因为票数很大，位数很长，所以可以用一个字符串表示票数，先比较票数的位数，位数相同时比较字典序

代码

#include<iostream>
#include<string>
using namespace std;
typedef struct ren {
	int num;
	string piao;
	int len;
}ren;
int main() {
	ren r[22];
	int n;
	cin >> n;
	ren max;
	max.len = 0;
	for (int i = 0; i < n; i++) {
		r[i].num = i + 1;
		cin >> r[i].piao;
		r[i].len = r[i].piao.size();
		if (r[i].len > max.len) {
			max.len = r[i].len;
			max.num = r[i].num;
			max.piao = r[i].piao;
		}
		else if (r[i].len == max.len && r[i].piao>max.piao) {
			max.len = r[i].len;
			max.num = r[i].num;
			max.piao = r[i].piao;
		}
	}
	cout << max.num << endl;
	cout << max.piao << endl;
	return 0;
}

P2676 Bookshelf B

[USACO07DEC] Bookshelf B - 洛谷

题目

解答

思路

因为要使叠加的奶牛的数量最少，所以先选择身高高的奶牛叠加，故而将奶牛由高到低排序

代码

#include<iostream>
#include<algorithm>
using namespace std;
int N, B;
int H[20005];
bool cmp(int a, int b) {
	return a > b;
}
int main() {
	int ans = 0, sum = 0;
	cin >> N >> B;
	for (int i = 0; i < N; i++)
		cin >> H[i];
	sort(H, H + N, cmp);
	while (sum < B) {
		sum += H[ans];
		ans++;
	}
	cout << ans;
	return 0;
}

P1116 车厢重组

车厢重组 - 洛谷

题目

解答

思路

冒泡排序中，数值交换的次数

代码

#include<iostream>
using namespace std;
int main() {
	int N;
	int ans = 0;
	cin >> N;
	int t[10010];
	for (int i = 0;i < N;i++)
		cin >> t[i];
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < i;j++) {
			if (t[j] > t[i])
				ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

P1152 欢乐的跳

欢乐的跳 - 洛谷

题目

解答

思路

依次计算两个连续元素之间差的绝对值，排序，与 1 ~ n-1 比较

PS：第一次使用映射记录两个连续元素之间差的绝对值，但是没有通过，因为两个数之间的差可能比1000大，所以将差映射到0~1000的数组内，差大于1000的无法实现映射

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int a[1005];
int b[1005];
int main() {
	bool ans= true;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n - 1; i++)
		b[i] = abs(a[i] - a[i + 1]);
	sort(b, b + n - 1);
	for (int i = 0; i < n-1; i++) {
		if (b[i] != i + 1) {
			ans = false;
			break;
		}
	}
	if (ans)
		cout << "Jolly" << endl;
	else
		cout << "Not jolly" << endl;
	return 0;
}

P1068 分数线划定

[NOIP2009 普及组] 分数线划定 - 洛谷

题目

解答

思路

根据要求排序，然后确定面试分数线，检查重分人员，重新计算实际进入面试的人数

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n, m;
typedef struct stu {
	int num;
	int grade;
}stu;
bool cmp(stu a, stu b) {
	if (a.grade == b.grade)
		return a.num < b.num;
	return a.grade > b.grade;
}
int main() {
	cin >> n >> m;
	stu s[5005];
	for (int i = 0; i < n; i++) 
		cin >> s[i].num >> s[i].grade;
	int ans = floor(m * 1.5);//向下取整
	int ans_s = ans;
	sort(s, s + n, cmp);
	for (int i = ans; i < n; i++) {//判断是否有重分
		if (s[i].grade != s[ans - 1].grade)
			break;
		else 
			ans_s++;
	}
	cout << s[ans - 1].grade << " " << ans_s << endl;
	for (int i = 0; i < ans_s; i++)
		cout << s[i].num << " " << s[i].grade << endl;
	return 0;
}

P5143 攀爬者

攀爬者 - 洛谷

题目

解答

思路

先根据 z 坐标将所有的点排序，然后依次通过所有点，并计算距离

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int N;
typedef struct dian {
	int x;
	int y;
	int z;
	bool state = false;
}dian;
bool cmp(dian a, dian b) {
	return a.z < b.z;
}
double jvli(dian a, dian b) {
	int x = abs(a.x - b.x);
	int y = abs(a.y - b.y);
	int z = abs(a.z - b.z);
	double q = x * x + y * y + z * z;
	double p = pow(q, 0.5);
	return p;
}
int main() {
	double sum = 0;
	cin >> N;
	dian a[50005];
	for (int i = 0; i < N; i++) {
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	sort(a, a + N, cmp);
	for (int i = 0; i < N-1; i++) {
		sum += jvli(a[i], a[i + 1]);
	}
	printf("%.3lf", sum);
	return 0;
}

P1104 生日

生日 - 洛谷

题目

解答

思路

创建 学生 结构体，记录编号（根据输入顺序进行编号），姓名，出生年、月、日，依据题目要求对学生结构体数组中的每个元素排序

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
typedef struct student {
	int num;
	string name;
	int y;
	int m;
	int d;
}student;
bool cmp(student a, student b) {
	if (a.y != b.y)
		return a.y < b.y;
	else {
		if (a.m != b.m)
			return a.m < b.m;
		else {
			if (a.d != b.d)
				return  a.d < b.d;
			else
				return a.num > b.num;
		}
	}
}
int main() {
	cin >> n;
	student s[105];
	for (int i = 0; i < n; i++) {
		cin >> s[i].name >> s[i].y >> s[i].m >> s[i].d;
		s[i].num = i;
	}
	sort(s, s + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << s[i].name << endl;
	}
	return 0;
}

P1012 拼数

[NOIP1998 提高组] 拼数 - 洛谷

题目

解答

思路

若要得到最大的整数，则需要 0~9 中的大数做高位，故而不是比较 ai 的大小，而是将 ai 作为字符串，比较字典序

现有 A 和 B，要使二者拼接后最大，则应该比较 A+B 与 B+A 的大小，据此对这 n 个整数进行排序，然后依次输出，即为 拼接后最大的整数

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s[25];
int n;
bool cmp(string a, string b) {
	return (a + b) > (b + a);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	sort(s, s + n, cmp);
	for (int i = 0; i < n; i++)
		cout << s[i];
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/404081.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

YOLOv9 | 利用YOLOv9训练自己的数据集 -＞ 推理、验证（源码解读 + 手撕结构图）

YOLOv9 | 利用YOLOv9训练自己的数据集 -＞ 推理、验证（源码解读 + 手撕结构图）

一、本文介绍 本文给大家带来的是全新的SOTA模型YOLOv9的基础使用教程&#xff0c;需要注意的是YOLOv9发布时间为2024年2月21日&#xff0c;截至最近的日期也没有过去几天&#xff0c;从其实验结果上来看&#xff0c;其效果无论是精度和参数量都要大于过去的一些实时检测模型&…
阅读更多...
智能水浸传感器拆解指导，水浸传感器有哪些种类？

智能水浸传感器拆解指导，水浸传感器有哪些种类？

很多朋友听说过智能水浸传感器&#xff0c;当我们的厨房或者卫生间发生漏水&#xff0c;只要提前安装放置好一个水浸传感器&#xff0c;哪怕我们身处外地也能发现并及时处理。除此之外&#xff0c;数据中心、机房、仓库、实验室、工厂、档案馆等也是智能水浸传感器的常见应用场…
阅读更多...
如何图片无损放大？分享两个无损放大方法

如何图片无损放大？分享两个无损放大方法

在数字化时代的洪流中&#xff0c;我们时常被细微之处的美丽所打动——那些精致的画面&#xff0c;那些清晰的细节。然而&#xff0c;随着图片的放大&#xff0c;我们常常面临一个难题&#xff1a;清晰度的损失。此时&#xff0c;图片无损放大软件能够在不损失图片质量的前提下…
阅读更多...
宝塔面板安装了mysql5.7和phpMyadmin，但是访问phpMyadmin时提示502 Bad Gateway

宝塔面板安装了mysql5.7和phpMyadmin，但是访问phpMyadmin时提示502 Bad Gateway

操作流程截图如下&#xff1a; 原因是没有选择php版本 选择php版本 下一页找到phpMyAdmin&#xff0c;选择设置 目前只有纯净态&#xff0c;说明没有php环境&#xff0c;前去安装php环境 点击安装&#xff0c;选择版本&#xff0c;这里选择的是7.4版本&#xff0c;编译安…
阅读更多...
设计模式六：策略模式

设计模式六：策略模式

1、策略模式 策略模式定义了一系列的算法&#xff0c;并将每一个算法封装起来&#xff0c;使每个算法可以相互替代&#xff0c;使算法本身和使用算法的客户端分割开来&#xff0c;相互独立。 策略模式的角色&#xff1a; 策略接口角色IStrategy&#xff1a;用来约束一系列具体…
阅读更多...
抖音爬虫批量视频提取功能介绍|抖音评论提取工具

抖音爬虫批量视频提取功能介绍|抖音评论提取工具

抖音爬虫是指通过编程技术从抖音平台上获取视频数据的程序。在进行抖音爬虫时&#xff0c;需要注意遵守相关法律法规和平台规定&#xff0c;以确保数据的合法获取和使用。 一般来说&#xff0c;抖音爬虫可以实现以下功能之一&#xff1a;批量视频提取。这个功能可以用于自动化地…
阅读更多...
【C++精简版回顾】7.析构函数

【C++精简版回顾】7.析构函数

1.析构函数 class MM { public:MM() {}MM(const char* a) {name new char[strlen(a)1];strcpy(name, a);cout << name << endl;}~MM() {delete[] name;name nullptr;cout << "调用析构函数" << endl;} private:char* name; }; int main(…
阅读更多...
论文摘要翻译 ，论文摘要怎么翻译成英文？

论文摘要翻译 ，论文摘要怎么翻译成英文？

论文摘要翻译在学术论文写作中扮演着至关重要的角色&#xff0c;它如同明灯&#xff0c;引领着读者快速理解论文的核心观点与目的。那么&#xff0c;如何才能将论文摘要翻译得恰到好处呢&#xff1f;这其中又蕴含着怎样的奥秘&#xff1f; 专家指出&#xff0c;摘要作为正式论文…
阅读更多...
使用uniapp实现小程序获取wifi并连接

使用uniapp实现小程序获取wifi并连接

一、背景 因业务需求&#xff0c;需要在小程序实现发现wifi和连接wifi。但由于Andriod和IOS有差异&#xff0c;所以实现起来有所区别。 先看官方文档 https://developers.weixin.qq.com/miniprogram/dev/framework/device/wifi.html 把连接基础流程了解后&#xff0c;发现二者…
阅读更多...
Jenkins的使用GIT（4）

Jenkins的使用GIT（4）

Jenkins的使用GIT 20211002 我们使用 Jenkins 集成外部 Git 仓库&#xff0c;实现对真实代码的拉取和构建。在这里&#xff0c;我们选用 Coding/Github/Gitee 等都可以作为我们的代码源 1 生成公钥私钥 首先&#xff0c;我们先来配置公钥和私钥。这是 Jenkins 访问 Git 私有库…
阅读更多...
springboot大学生体质测试管理系统源码和论文

springboot大学生体质测试管理系统源码和论文

大学生体质测试管理系统提供给用户一个简单方便体质测试管理信息&#xff0c;通过留言区互动更方便。本系统采用了B/S体系的结构&#xff0c;使用了java技术以及MYSQL作为后台数据库进行开发。系统主要分为系统管理员、教师和用户三个部分&#xff0c;系统管理员主要功能包括首…
阅读更多...
【高德地图】Android高德地图初始化定位并显示小蓝点

【高德地图】Android高德地图初始化定位并显示小蓝点

&#x1f4d6;第3章 初始化定位并显示小蓝点 ✅第1步&#xff1a;配置AndroidManifest.xml✅第2步&#xff1a;设置定位蓝点✅第3步&#xff1a;初始化定位✅完整代码 ✅第1步&#xff1a;配置AndroidManifest.xml 在application标签下声明Service组件 <service android:n…
阅读更多...
主流的开发语言和开发环境介绍

主流的开发语言和开发环境介绍

个人浅见&#xff0c;不喜勿喷&#xff0c;谢谢 软件开发是一个涉及多个方面的复杂过程&#xff0c;其中包括选择合适的编程语言和开发环境。编程语言是软件开发的核心&#xff0c;它定义了程序员用来编写指令的语法和规则。而开发环境则提供了编写、测试和调试代码的工具和平台…
阅读更多...
Shopee提现有哪些要求？提现到个人账户还是公司账户？站斧浏览器

Shopee提现有哪些要求？提现到个人账户还是公司账户？站斧浏览器

Shopee提现有哪些要求&#xff1f; 中国内地卖家提现至境内同名对公账户/法定代表人个人账户&#xff0c;支持所有主流银行、大部分农村信用社和村镇银行&#xff0c;部分银行需要提供联行号;中国香港卖家提现或付款到香港或全球银行账户&#xff0c;支持所有主流银行。 Shop…
阅读更多...
用友NC65与用友NCC对接集成NC65-凭证列表查询打通凭证新增

用友NC65与用友NCC对接集成NC65-凭证列表查询打通凭证新增

用友NC65与用友NCC对接集成NC65-凭证列表查询打通凭证新增 数据源平台:用友NC65 用友NC是为集团与行业企业提供的全线管理软件产品&#xff0c;由亚太本土最大的企业管理软件提供商用友公司研发提供&#xff0c;用友NC率先采用J2EE架构和先进开放的集团级开发平台UAP&#xff0…
阅读更多...
适用于生物行业的样本管理系统

适用于生物行业的样本管理系统

在生物样本管理系统的应用中&#xff0c;我们首先需要了解生物样本的特点和要求。生物样本具有多样性和易变性&#xff0c;需要被妥善保存和跟踪&#xff0c;以确保其质量和可用性。 因此&#xff0c;一个有效的生物样本管理系统需要具备以下特点&#xff1a; 全面性&#xff1…
阅读更多...
深度剖析Selenium与Scrapy的黄金组合：实现动态网页爬虫

深度剖析Selenium与Scrapy的黄金组合：实现动态网页爬虫

在当今互联网时代&#xff0c;大量网站采用动态网页技术呈现信息&#xff0c;这给爬虫技术提出了新的挑战。本文将带您深入探讨如何应对动态网页的爬取难题&#xff0c;结合Python爬虫框架Scrapy和自动化测试工具Selenium进行实战&#xff0c;为您揭示动态网页爬取的技术奥秘。…
阅读更多...
现货黄金短线走高是机会还是风险？

现货黄金短线走高是机会还是风险？

在投资市场上&#xff0c;短线交易一般是指投资者在两三个交易日或一两个星期内&#xff0c;通过低买高卖获取差价收益的买卖行为。做短线交易的人&#xff0c;一旦价格到达自己的止损位置就会果断地离场&#xff0c;然后重新等待入市的机会&#xff0c;或者直接参与其他的品种…
阅读更多...
链表 任意位置插入一个节点

链表 任意位置插入一个节点

那么&#xff0c;内存中发生了什么事情呢&#xff1f; 当程序开始执行时&#xff0c;最初将调用main函数&#xff0c;栈中的部分内存被分配用于执行函数。 所有局部变量以及该函数的执行状态都保存在这个特定的区域&#xff0c;我们也将其称为函数的栈帧。 在此main函数中&…
阅读更多...
【FreeRTOS基础入门】软件定时器

【FreeRTOS基础入门】软件定时器

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、软件定时器的介绍1.1 软件定时器的特性1.2 软件定时器的特性1.3 守护任务 二、软件定时器的使用2.1 回调函数2.2 创建定时器创建动态定时器创建静态定时器 …
阅读更多...
最新文章

Copyright @ 2022~2023