【Ural 1010】 Discrete Function(枚举+找规律)

02
Sep

【Ural 1010】 Discrete Function(枚举+找规律)

同样也是黑书的题,第一小节练习题。当时想的是用双指针做,但是在最优取舍策略上一直没有收获。于是尝试从题目本身的规律上入手,最后成功解出。如果找对了方向,其实这题就是水题,嘛,可惜我还是花了很久才做出来,还是记录一下吧。

题面描述
给定一个定义在[1,n]上的函数值序列,这个函数是离散的,仅在每个x为整数的坐标处有取值,也就是说实际上给出了这个函数的图像。现要求在整个图像上取两点,并在这两点之间画一条直线。要求在这两个点之间所有的函数点均在这条直线的下方。问可以取到的直线的斜率最大时,所取的两个点的坐标。
解题思路
一眼看过去就感觉很麻烦,首先两点间所有点均在这两点连线下的条件就有些诡异和难以操作,而且单是枚举两个点的过程时间复杂度就很高。这种情况下,应该考虑到题目本身的性质。可以采用打表等方式构造几组数据手算一下,发现解的值永远是一堆相邻点。那么假设题目的解是差的绝对值最大的一对相邻点,我们来尝试证明:
采用反证法,设l,r是题目的解,且l,r不相邻。

那么线段lr的斜率的绝对值就是(f(r)-f(l))/(r-l),令其等于k。为方便考虑,我们令这个函数单调不减,且均为正。那么很容易发现,两个相邻点之间的线段斜率为f(i+1)-f(i),令其等于g(i)。因为l和r不是相邻点,所以对于区间内所有g(i),均不超过k。

考虑r-l=2的情况,即l和r之间只隔了两个点,则f(r)-f(l)=2k;f(r)-f(l)=f(r)-f(l+1)+f(l+1)-f(l)=g(l)+g(l+1);由于区间内所有g(i)均小于k,所以g(l)+g(l+1)<2k,命题不成立。很容易可以将其推广到r-l=n的情况,也就是说,l和r必为相邻点,接下来就没什么难度了。
代码编写
没有什么难度,枚举每一个相邻点对的差的绝对值,取最大即可。
AC代码
https://paste.ubuntu.com/25446191/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论