A Fast Forwarding


题意:给你一个放音机,上面有1/3倍的按钮和3倍速度的按钮,按按钮的间隔至少为1s,现在问最短需要多久可以到给定的n的位置


解答,观察可知,\( 3^0 \)至少出现一次,如果最高是\( 3^k \)的话,那么\( 3^1 \)一直到\( 3^{k-1} \)都必须至少出现两次,方法的话可以转换成三进制,然后计算进位即可,即:第一位至少要是1,其他位至少要是2,不满足的情况向高位借位



B Estimating the Flood Risk


题意:给定一个图(w*d),下面有n个点,对于每一个点有一个高度,相邻的点高度差不能大于1,现在问整张图的最小高度和是多少


解答:考虑到数据范围很小\( 1 \leq w,d,n \leq 50 \),所以我们可以采用暴力算法

考虑优先队列+bfs的方法,每次使得高度最高的点优先出队,搜索到周围的所有点,高度-1,这样构造出的图一定是满足条件的高度最小的图,然后判断一下是否存在相邻的高度不满足题意的问题,满足题意求和输出即可


 

分类: BFS模拟

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注