Llf's blog

标签 排序 下的文章

Llf in 题解
February 8, 2018

题解-洛谷P1309 瑞士轮

原题链接 洛谷博客该题解链接 题目内容 题目背景 在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。 本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中,既保证了比赛的稳定性,又能使赛程不...
February 7, 2018

几种排序方法总结

冒泡排序 方法 第一次将每一个元素和它的后一个元素比较大小,如果不满足顺序则交换,这样即可确定最后一个数的位置。然后再从头开始,可以确定倒数第二个数的位置。循环n次后即可完成排序。因为每一轮排完序后都会确定一个,即“冒”出来一个,故被称作冒泡排序。 时间效率:$O(n^{2})$ 代码 以 洛谷 P1116 车厢重组 为例 #include<bits/stdc++.h> usi...
February 6, 2018

拓扑排序

概念 拓扑排序是一种可以将有先决条件(即必须将a、b排在前面后再排c,缺一不可)的数据变得有序的一种排序方法。拓扑排序仅可在有向无环图中使用,同时可以判断图中是否有环。因为顺序不同,拓扑排序得到的答案可能不同。 思路 因为排序是有先决条件的,所以可以将要有先决条件的个数(在图中即为入度)记录下来,每满足一个就减一,直到个数为0便可以将其放入序列中。 手动实现 如果我们有如下的一个有向无环图,...