发布于2021-12-23

2016年第七届蓝桥杯省赛-I. 交换瓶子

原创 100阅读 数据结构与算法

有 N 个瓶子,编号 1 ~ N,放在架子上。 比如有 5 个瓶子: 2 1 3 5 4 要求每次拿起 2 个瓶子,交换它们的位置。 经过若干次后,使得瓶子的序号为: 1 2 3 4 5 对于这么简单的情况,显然,至少需要交换 2 次就可以复位。 如果瓶子更多呢?你可以通过编程来解决。

发布于2021-12-13

2014年第五届蓝桥杯省赛-J. 小朋友排队

原创 128阅读 数据结构与算法

n个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候,所有小朋友的不高兴程度都是 0。 如果某个小朋友第一次被要求交换,则他的不高兴程度增加 1,如果第二次要求他交换,则他的不高兴程度增加 2(即不高兴程度为 3),依次类推。当要求某个小朋友第 k 次交换时,他的不高兴程度增加 k。 请问,要让所所有小朋友按从

发布于2021-03-04

AcWing-123-士兵

原创 135阅读 数据结构与算法

格格兰郡的N名士兵随机散落在全郡各地。格格兰郡中的位置由一对 (x,y) 整数坐标表示。士兵可以进行移动,每次移动,士兵可以向上,向下,向左或向右移动一个单位(因此,他的x或y坐标也将加1或减1)。现在希望通过移动士兵,使得所有士兵彼此相邻的处于同一条水平线内,即所有士兵的y坐标相同并且x坐标相同。

发布于2021-02-18

AcWing-109-天才ACM

原创 76阅读 数据结构与算法

给定一个整数 M,对于任意一个整数集合 S,定义“校验值”如下:从集合 S 中取出 M 对数(即 2∗M 个数,不能重复使用集合中的数,如果 S 中的整数不够 M 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 S 的“校验值”。

发布于2021-02-14

AcWing-108-奇数码问题

原创 68阅读 数据结构与算法

你一定玩过八数码游戏,它实际上是在一个3×3的网格中进行的,1个空格和1~8这8个数字恰好不重不漏地分布在这3×3的网格中。在游戏过程中,可以把空格与其上、下、左、右四个方向之一的数字交换(如果存在)。

发布于2021-02-14

信息学竞赛模板(五)— 归并排序

原创 80阅读 数据结构与算法

归并排序算法实现模板。

发布于2021-02-14

AcWing-107-超快速排序

原创 60阅读 数据结构与算法

在这个问题中,您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理n个不同整数的序列,直到序列按升序排序。对于输入序列`9 1 0 5 4`,超快速排序生成输出`0 1 4 5 9`。您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

发布于2021-02-14

信息学竞赛模板(四)— 快速选择(排序)

原创 82阅读 数据结构与算法

利用分治的思想,在 `[l, r]` 中随机选取一个基准值,将其他位置的数与基准值相比较,若比基准值小,放到基准值位置的左边,否则放在基准值位置的右边,再递归基准值左边区间和基准值右边区间,又进行上述操作,直到区间大小为2时,则直接比较两个元素的大小位置进行位置交换,区间大小为1时,直接返回该区间。

发布于2021-02-14

AcWing-106-动态中位数

原创 90阅读 数据结构与算法

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

发布于2021-02-10

AcWing-105-七夕祭

原创 57阅读 数据结构与算法

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去TYVJ七夕祭游玩。TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。