Yao Lirong's Blog

Yao Lirong's Blog

Innovation For Everyone

P1031 均分纸牌

题目来源:洛谷P1031 均分纸牌


标解

注意本题中平均数的运用

首先,一定要想到每堆排的张数减去平均张数,这样,题目就变成了移动正数,加到负数中,是大家都变成了0,这就意味着成功了60%!!!!(关键)。以例题来说,平均张数为10,原张数变为-1,-2,+7,-4,因为没有为0的数,所以从最左边出发,将-1移动到-2中,变为0,-3,+7,4,再讲-3向右移动……一次类推,直到全为0为止。没移动一次,步数便加1。关键是,负数怎么移动,其实,移动-x张牌,其实就是从另一堆中移动x张牌,步数相同。还有就是要过滤0,如排数为4,4,2,6,则减去平均数后为0,0,-2,2,就要从第三对开始移动。注意有些0是不能过滤的,如1,0,1,-2中的0。还有就是每次移动好都要过滤。如-2,2,1,3,-4,第一步后变为0,0,1,3,-4,可以省略第二堆的移动。

P2678 跳石头

题目来源:洛谷P2678 跳石头


这是一道标准的 “最大值最小”或“最小值最大“ 的题,遇到这种题,我们就可以使用 贪心+二分查找 的方法来做

二分答案/二分查找

有序(单调)的,有界的就可以用二分法查找。

P1090 合并果子

题目来源: 洛谷P1090 合并果子


一维数组做法

本题是一个简单的 Huffman树。Huffman编码 在 UTF-8 & Unicode 中都有它思想的体现,即出现频率高的编码长度短,出现频率低的编码长度长,用以缩短整体编码长度

这里我也运用了前面 P1309 的思想:因为每次需要重新排序的时候只有一个数据需要被插入整个数列当中,所以并不需要假定数据无序的 quick sort,反而是线性的排序更快

P1309 瑞士轮

题目来源:洛谷P1309 瑞士轮


  1. 胜者组和败者组分别是有序的,使用 mergesort 将两个有序同向数组进行归并(严格上来说不是归并排序),大大降低了时间复杂度 = O(n)。如果我们使用 quicksort,则默认整个数据是无序的,对每个数据都重新排序所以会超时
Introduction to Git Command

Creating repository

  • git init: create a repository
  • git add File_Name: add “File_Name” to repository
  • git add . : add all files
  • git commit -m "message": commit changes and tell others what changes have been made
  • git commit -m "Title" -m "Description ..": commit with a short title then long description
avatar
姚立嵘 Yao
让每个人享受科技的乐趣 (Innovation For Everyone)