1453B Suffix Operations(思维)

题目

题意：我们对于一个n个整数的数组a,可以进行两种操作：
1.对于它的任意长度后缀全体增加1.
2.对于它的任意长度后缀全体减少1.
并且我们还拥有一次改变数组a中一个整数变为任意整数的机会，但也可以不改变。求我们进行操作使数组每个整数相等的最小操作数。

思路：当我们还没使用改变数组中的整数的机会时，我们所求的最小操作数为数组中所有相邻元素相差之和，如1 3 5 7
如果我们想使最后两个元素5 7变成相同那我们只有单独改变7 变 6 变 5，成为1 3 5 5，如果我们从5（或更前面的1 3）开始增或减的话 会变为1 3 6 8 / 1 3 4 6 可以发现这样无论如何都不会使之相等所以我们只有先将7单独变为5，然后再从后往前将1 3 5 5->1 3 3 3->1 1 1 1。这样我们求得最小的即为相邻元素差值总和。

但我们还有一个条件没用，就是改变一个元素，很容易想到我们肯定是将要改变的元素变为和相邻的元素相等，那么我们可以遍历所有元素都将其变为和临近元素相等，然后找出谁贡献的最多的那个元素将其改变，用sum减去其贡献的。如 3 2 11 9 假设将2变为3 （3 3 11 9）那么 原本需要操作（2-3）+（11-2）次现在只需操作11-3次，贡献值为2，还有首尾特殊考虑一下。

Code

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 3e5 + 5;
ll lst[Max];
int Mod = 1e9 + 7;

int main()
{
   
	int t;cin >> t;
	while (t--)
	{
   
		int n;cin >> n;
		ll sum = 0, p = -1e18+5;
		for (int i = 1;i <= n;i++)cin >> lst[i];
		for (int i = 2;i <= n ;i++)
		{
   
			sum += abs(lst[i] - lst[i - 1]);
			if (i == n)continue;
			p = max(abs(lst[i] - lst[i - 1]) + abs(lst[i + 1] - lst[i])-abs(lst[i-1]-lst[i+1]), p);
		}
		p = max(p, abs(lst[2] - lst[1]));
		p = max(p, abs(lst[n] - lst[n - 1]));
		p = max(ll(0), p);
		cout << sum - p << endl;
	}
}