游游的平滑数列

[编程题]游游的平滑数列

热度指数：201 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游得到了一个有 $n$ 个数字的数列。

游游定义了 “平滑值”的概念：平滑值指任意两个相邻的数的差的绝对值的最大值。例如[1,2,5,7,8]的平滑值是3。

游游现在想知道，在只修改一个位置的数字（可以修改为任意值）或者不修改的情况下，数列的平滑值最小是多少？

输入描述:

第一行包含一个数字 ，代表数列的数字个数。
第二行包含  个数字，代表数列 ，数列中的数字满足 。

输出描述:

输出一个整数，代表数列最小的平滑值。

示例1

输入

3
1 3 4

输出

说明

将第一个数字修改为  ，平滑值变为 ，可以证明这是最优的方案之一。

示例2

输入

5
-1 1 2 5 7

输出

说明

将第三个数字修改为  ，平滑值变为 。这是唯一的修改方式。

算法知识视频讲解

C/C++

烦恼的伊泽瑞尔不讲武德

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int N = 2e5 + 10, inf = 2e9 + 10;

int n;
int a[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
map<int, int> hash;
for (int i = 1; i < n; i ++ ) hash[abs(a[i] - a[i + 1])] ++;
int ans = inf;
for (int i = 1; i <= n; i ++ )
{
if (i == 1 || i == n)
{
int t;
if (i == 1) t = abs(a[i] - a[i + 1]);
else t = abs(a[i] - a[i - 1]);
hash[t] --;
if (hash[t] == 0) hash.erase(t);
hash[0] ++;

ans = min(ans, hash.rbegin()->first);

hash[t] ++;
hash[0] --;
if (hash[0] == 0) hash.erase(0);
}
else {
int d1 = abs(a[i] - a[i - 1]), d2 = abs(a[i] - a[i + 1]);
hash[d1] --;
hash[d2] --;
if (hash[d1] == 0) hash.erase(d1);
if (hash[d2] == 0) hash.erase(d2);
int t = (a[i - 1] + a[i + 1]) / 2;
int t1 = abs(t - a[i - 1]), t2 = abs(t - a[i + 1]);
hash[t1] ++;
hash[t2] ++;

ans = min(ans, hash.rbegin()->first);

hash[d1] ++;
hash[d2] ++;
hash[t1] --;
hash[t2] --;
if (hash[t1] == 0) hash.erase(t1);
if (hash[t2] == 0) hash.erase(t2);
}
}

cout << ans << endl;

return 0;
}

发表于 2023-09-06 23:43:05 回复(0)