小牛博客

¶首先来首歌曲来放松一下吧！ 题目链接：107. 超快速排序 ¶题目背景： 又是归并排序求逆序对的问题！ 参考我关于这类问题的一篇题解：AcWing-788.逆序对的数量 ¶题目描述 在这个问题中，您必须分析特定的排序算法----超快速排序。 该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。 对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。 您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。 ¶输入格式 输入包括一些测试用例。 每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。 接下来n行每行输入一个整数ai,代表用例中输入序列的具体数据，第i行的数据代表序列中第i个数。 当输入用例中包含的输入序列长度为0时，输入终止，该序列无需处理。 ¶输出格式 对于每个需要处理的输入序列，输出一个整数op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。 ¶数据范围 0≤N<500000 0≤ai≤999999999 ¶输入样例： 12345678910115910543 ...

¶首先来首歌曲来放松一下吧！ 题目链接：106. 动态中位数 ¶题目背景： 让两个堆来构建一个有序序列，找到中位数，优先队列的优先就是用堆结构实现的！ ¶题目描述 依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。 ¶输入格式 第一行输入一个整数P，代表后面数据集的个数，接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表数据集的编号的整数。 然后输入一个整数M，代表数据集中包含数据的个数，M一定为奇数，数据之间用空格隔开。 数据集的剩余行由数据集的数据构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。 ¶输出格式 对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。 数据集的剩余行由输出的中位数构成，每行包含10个数据，最后一行数据量可能少于10个，数据之间用空格隔开。 输出中不应该存在空行。 ¶数据范围 1≤P≤1000 1≤M≤9999 ¶输入样例： 1234567893 1 9 1 2 3 4 5 6 7 ...

¶首先来首歌曲来放松一下吧！ 题目链接：122. 糖果传递 ¶题目背景： 又是一道环形的均分纸牌问题，这也是这类题的一个基础的经典的例题了！ 我先做的 七夕祭 这道题，一个二维的环形均分纸牌问题，比这个复杂一点。。 ¶题目描述 有n个小朋友坐成一圈，每人有a[i]个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为1。 求使所有人获得均等糖果的最小代价。 ¶输入格式 第一行输入一个正整数n，表示小朋友的个数。 接下来n行，每行一个整数a[i]，表示第i个小朋友初始得到的糖果的颗数。 ¶输出格式 输出一个整数，表示最小代价。 ¶数据范围 1≤n≤1000000 数据保证一定有解。 ¶输入样例： 1234541254 ¶输出样例： 14 ¶题目分析： ¶题目要求： n个人围成一圈，没人有一些糖果，问最少交换多少次会达到均等时的最小步数！ 传递一个糖果代价为1！ ¶解题思路： 同样是环形均分纸牌问题，里面的公式推导就不再推了，请看我的上一篇题解： AcWing-105.七夕祭 接下来总结一下环形纸牌问题： 第一步：将原值减去平均值 第二步：求当前的前 ...

¶首先来首歌曲来放松一下吧！ 题目链接：105. 七夕祭 此题为了理解折腾了一下午，写题解又写了一晚上！终于完整的记录了下来 ¶题目背景： 本题运用了大量的数学公式化简，以及中位数性质等等，我会在题目分析当中进行详细介绍和解释！ ¶题目描述 七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。 于是TYVJ今年举办了一次线下七夕祭。 Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。 TYVJ七夕祭和11区的夏祭的形式很像。 矩形的祭典会场由N排M列共计N×M个摊点组成。 虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。 Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。 不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。 两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。 由于zhq率领的TYVJ开发小组成功地扭曲了空间 ...

¶首先来首歌曲来放松一下吧！ ¶题目背景： ¶题目描述 在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。 1 2 … 26 27 28 … a b … z ab ac … 对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。 ¶算法设计： 对于给定的长度不超过6的升序字符串，计算出它在上述字典中的编码。 ¶输入格式 第一行是一个正整数k，表示接下来共有k行。 接下来的k行中，每行给出一个字符串。 ¶输出格式 输出共有k行，每行对应于一个字符串的编码。 ¶数据范围 1≤n≤100000 ¶输入样例： 1232aab ¶输出样例： 12127 ¶题目分析： ¶题目要求： 输入一个字典序字符串，输出对应的编号，注意没有aa，abccd， ...

¶首先来首歌曲来放松一下吧！ 题目链接：104. 货仓选址 ¶题目背景： 贪心，贪的我很服。。。 ¶题目描述 在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。 ¶输入格式 第一行输入整数N。 第二行N个整数A1~AN。 ¶输出格式 输出一个整数，表示距离之和的最小值。 ¶数据范围 1≤N≤100000 ¶输入样例： 1246 2 9 1 ¶输出样例： 112 ¶题目分析： ¶题目要求： 有N个商店，要求放一个仓库使得到所有商店的距离和最小，输出最小值！ ¶解题思路： 第一想法就是暴力扫描一遍，选出最小值即可！但是超时了，数据范围为1e5，平方就是1e10，肯定超时，详见题解一的代码： 正确思路： 先排序，使其变成一条链状的情况！ 把a[0] ~ a[N-1]排序，设货仓在X坐标处，X左侧的商店有P家，右侧的商店有Q家。若P < Q，则每把仓库的选址向右移动1单位距离，距离之和就会变少Q - P.同理，若 ...

¶首先来首歌曲来放松一下吧！ 题目链接：102. 最佳牛围栏 ¶题目背景： 一道难题，前缀和，差分，双指针的叠加应用！ ¶题目描述 农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。 约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。 在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。 ¶输入格式 第一行输入整数 N 和 F ，数据间用空格隔开。 接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第i片区域内包含的牛的数目。 ¶输出格式 输出一个整数，表示平均值的最大值乘以1000再 向下取整 之后得到的结果。 ¶数据范围 1≤N≤100000 1≤F≤N ¶输入样例： 123456789101110 66 4210385941 ¶输出样例： 16500 ¶题目分析： ¶题目要求： 给了N块地，每块地有一些牛，现在想让你在1 ~ N 块地里，连续的选取大于 f 块地， ...

¶首先来首歌曲来放松一下吧！ 题目链接：101. 最高的牛 ¶题目背景： 差分应用！ ¶题目描述 有 N 头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。 当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。 现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。 但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。 求每头牛的身高的最大可能值是多少。 ¶输入格式 第一行输入整数N,P,H,M，数据用空格隔开。 接下来M行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。 ¶输出格式 一共输出 NN 行数据，每行输出一个整数。 第 ii 行输出的整数代表第 ii 头牛可能的最大身高。 ¶数据范围 1≤N≤10000 1≤H≤1000000 1≤A,B≤10000 0≤M≤10000 ¶输入样例： 1234569 3 5 51 35 34 33 79 8 ¶输出样例： 123456789545344555 ¶注意： 此题中给出的关系对可能存在 ...

¶首先来首歌曲来放松一下吧！ 题目链接：100. 增减序列 ¶题目背景： 前缀和和差分序列是互逆的！ 题目分析处详细解释！ ¶题目描述 给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。 ¶输入格式 第一行输入正整数n。 接下来n行，每行输入一个整数，第i+1行的整数代表ai。 ¶输出格式 第一行输出最少操作次数。 第二行输出最终能得到多少种结果。 ¶数据范围 0<n≤105 0≤ai<2147483648 ¶输入样例： 1234541122 ¶输出样例： 1212 ¶题目分析： ¶题目要求： 在一个序列内任意选择区间，将区间内的数都进行加一或减一操作，使得最后的序列数字都一样，问对少步数和达到最少步数的方法总数！ ¶解题思路： 先引入差分： a数组是普通序列，b数组是a数组的差分序列！ 差分序列定义：b[i] = a[i] - a[i-1], b[1] = a[1] 然后 ...

¶首先来首歌曲来放松一下吧！ 题目链接：99. 激光炸弹 ¶题目背景： ¶题目描述 地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。 注意：不同目标可能在同一位置。 现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有的目标。 激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y轴平行。 若目标位于爆破正方形的边上，该目标不会被摧毁！ 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 ¶输入格式 第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。 接下来N行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标和价值，数据用空格隔开。 ¶输出格式 输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。 ¶数据范围 0≤ R ≤109 0< N ≤10000 0≤ Xi,Yi ≤5000 0≤ Wi ≤1000 ¶输入样例： 1232 10 0 11 1 1 ¶输出样例： 11 ¶题目分 ...

¶首先来首歌曲来放松一下吧！ 题目链接：96. 奇怪的汉诺塔 ¶题目背景： ¶题目描述 汉诺塔问题，条件如下： 1、这里有A、B、C和D四座塔。 2、这里有n个圆盘，n的数量是恒定的。 3、每个圆盘的尺寸都不相同。 4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。 5、我们需要将所有的圆盘都从塔A转移到塔D上。 6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。 请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。 汉诺塔塔参考模型 ¶输入格式 没有输入 ¶输出格式 对于每一个整数n(1≤n≤121≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行。 ¶输入样例： 1没有输入 ¶输出样例： 1参考输出格式 ¶题目分析： ¶题目要求： 此题是三根柱子汉诺塔的变形，现在有四根棍子，需要输出n 为1 到12的最小移动次数即可！ ¶解题思路： 先介绍一下三根棍子情况：不论有多少个碟子，都可看为这几步： 将前n - 1 个盘子移到第二个棍子 再将最底下的1个盘子移到第三个棍子 再将n - ...

¶首先来首歌曲来放松一下吧！ 题目链接：95.费解的开关 ¶题目背景： ¶题目描述 你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态 123451011101101101111000011011 在改变了最左上角的灯的状态后将变成： 123450111111101101111000011011 再改变它正中间的灯后状态将变成： 123450111111001110011010011011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。 ¶输入格式 第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。 以下若干行数据分为nn组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。 ¶输出格式 一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入 ...