题解 | #求最大值#

题号：NC14402

链接：https://ac.nowcoder.com/acm/problem/14402 来源：牛客网

题目描述给出一个序列，你的任务是求每次操作之后序列中（a[j]-a[i]）/（j-i）【1<=i<j<=n】的最大值。操作次数有Q次，每次操作需要将位子p处的数字变成y.

思路: 本来以为是dp动态解决的，但是好像找不到dp公式（可能太菜）。

后来仔细看下，这个公式（a[j]-a[i]）/（j-i）【1<=i<j<=n】怎么看起来这么熟悉呢？

这不就是求导公式吗？导数就是函数斜率。

证明：分母必然是1.

随便画个散数函数图，假设其中两个点AB之间的斜率为最大，那么在中间的点C，如果在该直线AB上，那么分母可以缩小到中间点AC或者CB。如果不在直线上，比如C点在直线上面，那么AC的斜率大于AB，如果C点在直线下面，那CB的斜率大于AB，与假设矛盾。所以，不会出现中间点C，处于直线AB的上面或者下面。必然在AB之间，由于AB和AC的斜率一样，直接取AC。显然，必然最大斜率中，必然存在分母（j-i）是1.

其他都很简单了。假设i点和i+1点的斜率最大。初始化时候暴力求出i点即可。每一次查询Q，可以采用dp逻辑思路。

dp[i]=a[i+1]-a[i]

1.如果改变位置x跟i和i+1无关，其中最大斜率必然是max(dp[i],dp[x],dp[x-1]),x>=1,x<=n,x<>i,x<>i+1

2.如果改变位置x跟i和i+1有关。最大斜率可以直接暴力max(dp[1],dp[2],...dp[n])

注:

参考下测试数据:

2 4 6 8 10

2 5

2 4

输出:

3.00

2.00

用cin耗时会多三倍，如果超时，可能是使用cin导致的

附代码:

```#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int data2[300000];
int n,q;
// 获得最大斜率的那个最小索引
int find() {
	int maxValue= data2[1] - data2[0];
	int index = 0;
	for (int i=0; i < n-1; i++) {
		if (data2[i + 1] - data2[i] > maxValue) {
			maxValue = data2[i + 1] - data2[i];
			index = i;
		}
	}
	return index;
}
int main() {
	while (scanf("%d",&n) > 0) {
		for (int i = 0; i < n; i++) cin >> data2[i];
		cin >> q;
		int index;
		int x, y;
		index = find();
		int lastMax = data2[index + 1] - data2[index];
		for (int i = 0; i < q; i++) {
			scanf("%d%d", &x, &y);
			x = x - 1;
			data2[x] = y;
			// 如果破坏之前的
			if (x == index || index + 1 == x) {
				index = find();
				lastMax = data2[index + 1] - data2[index];
			}
			// 当前作为最小下标
			if (x + 1 < n && data2[x + 1] - data2[x] > lastMax) {
				index = x;
				lastMax = data2[index + 1] - data2[index];
			}
			// 当前作为最大下标
			if (x > 0 && data2[x] - data2[x - 1] > lastMax) {
				index = x - 1;
				lastMax = data2[index + 1] - data2[index];
			}
			printf("%.2lf\n", (double)lastMax);
		}
	}
}