旅行

Posted on Edited on In

题目大意：小Y得到了一个长度为n的序列a

选定一个区间 \([l,r] (l\not=r)\) ，设区间中的最大值为x，最小值为y，则他定义该区间的价值为 \(\dfrac {x-y} {r-l}\)。现在，他想让你找出这个序列价值最大的区间。你只需输出最大的价值下取整的结果。

这道题目和“计数”长得挺像，但是做法却一点也不同

首先我们可以发现，最优解的那个区间，其最大/小值一定在两个端点（可以反证）

那么最大值就会变成\(\dfrac{abs(a_l -a_r)}{r-l}\)，这个式子挺像文化课里面算斜率的那个式子

所以我们可以大胆假设，把\((i,a_i)\)看成二维平面的点，求两点间斜率的最大值

这时候，显然所有的点都在凸包上，再画个图就可以发现，我们只需要考虑最近的两个点

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 66;

int a[N];

signed main()
{
    int T = read();
    while (T --)
    {
        int i, n = read();
        int maxv = 0;
        a[0] = read();
        for (i = 1; i < n; ++ i)
        {
            a[i & 1] = read();
            if (abs(a[0] - a[1]) > maxv)
               maxv = abs(a[0] - a[1]); 
        }
        put(maxv);
    }
    return 0;
}