codeforces 479D. Long Jumps

http://codeforces.com/problemset/problem/479/D

题意是说有一把尺子,本身有一些刻度,然后需要测量x和y,问最少需要添加多少个刻度,如果需要,这些刻度分别添加在什么位置。

 

一开始没有看清题目,以为答案最多为4,但是发现,a[1]=0 a[n]=l这两个是确定的,所以答案最多为2,

而不会出现中间有两个刻度,无论是往前刻还是往后都会越界的情况。

先去看看已知的刻度里有没有直接满足的。

除此之外,如果在已知的刻度下无法测量x也无法测量y,我们还可以找找是否能有公用点使得只刻一个刻度就可以满足题意。公用点分两种情况,一种是在两个刻度之间,另一种是在两个刻度的同侧。

前一种没什么坑,后一种要判断是否越界!!!

如果在已知的刻度下能测量x或者能测量出y但不能同时测量的话,就没有必要找公用点。

 

还有就是查找的话如果线性找复杂度是O(n2),会TLE在第27个点。

我们用二分…

话说STL里竟然连二分查找也有。。。。简直orz。。。。真是省时省力。

 

代码:

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz