0%

比赛链接: http://codeforces.com/contest/439

A题(Devu, the Singer and Churu, the Joker)

题目大意:

Devu 喜欢唱歌,唱一首歌的时间为 t, 每唱完一首歌至少要休息 10 分钟,Churu 喜欢讲笑话,讲一个笑话的时间为 5 分钟, 现给定两个整数 $n(1 <= n <= 100) d(1 <= d <= 10000)$, 分别表示Devu在个人演唱会上要唱 n 首歌,演唱会的总时间为 $d$, 接下来给定$n$个整数表示 $t_i(1 <= t <= 100)$, 表示这$n$首歌的时间,问在保证 Devu 把所有歌唱完的情况下,Churu 最多可以讲多少个笑话,如果 Devu 不能把 $n$ 首歌唱完,输出 -1.

阅读全文 »

比赛链接: http://codeforces.com/contest/435

A题(Queue on Bus Stop)

题目大意:

已知每辆公交车最多可以载 $m(1 <= m <= 100)$ 个人,给出 $n(1 <= n <= 100)$ 组人, 人数分别为 $a_i(1 <= i <= m)$, 每辆公交车尽量可以载更多的组, 但是不能把每组人分开载, 问把这 $n$ 组人全部载上最少需要多少辆公交车。注意: 要按顺序一组一组的上车。

阅读全文 »

快速排序法

概述

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.

阅读全文 »

概述

最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:

阅读全文 »

最小生成树

概述

在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即)且为无循环图,使得 的 w(T) 最小,则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。 许多应用问题都是一个求无向连通图的最小生成树问题。例如:要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

阅读全文 »

并查集

概述

并查集是一种用来管理元素分组情况的数据结构。冰茶既可以高效的进行如下操作。不过需要注意并查集虽然可以进行合并操作,但是却无法进行分割操作。 并查集可以查询元素a和元素b是否属于同一组。 并查集可以合并元素a和元素b所在的组。

阅读全文 »