1453B Suffix Operations(思维)

叁歲伎倆 2021-07-16 23:16 262阅读 0赞

[题目][Link 1]

题意：我们对于一个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;
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1453/B