Codeforces Round #688 (Div. 2) B：Suffix Operations （差分，贪心）

一时失言乱红尘 2022-12-26 14:26 140阅读 0赞

原题链接：[B：Suffix Operations][B_Suffix Operations]

### 原题 ###

![b][]

### 题目大意 ###

给n个数，有两种操作，一是选定一个数x，将x和x之后的所有数加1；二是选定一个数x，将x和x之后的所有数减1。现在你有一次机会可以在开始操作之前将任意一个数修改成任意的一个数（修改不算操作次数），问最少多少次操作可以将原数组变成相同的数。

### 思路 ###

看到最小后缀操作次数，很容易 就想到了差分。如果不看这次修改的话，问题就很简单，要使整个数组相等，就等于将原数组的差分数组除了第一位之后的每一位变成0。那么最小操作次数就是差分数组除了第一位之后的**每一位的绝对值之和**。  
但是现在多了一次修改，那么我们就得找到修改哪一个数，减少的操作次数最多，我们就修改这个数。为了使操作次数最少，我们肯定是将这个数修改成和前一个数相等的数，因此修改第i个数减少的操作次数就是**第i+1个数和第i个数的差的绝对值加上第i个数和第i-1个数差的绝对值，减去第i+1个数和第i-1个数的差的绝对值**。（节省的操作次数就是修改之前的次数减去修改之后的次数）  
放在差分数组里，减少的次数就是b\[i\]+1的绝对值加上b\[i\]的绝对值减去(b\[i+1\]+b\[i\])的绝对值。（对于第一个数和最后一个数要特别判断）

### ac代码 ###

#include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 200010;
    typedef long long ll;
    
    ll n,a[N],b[N],sum,maxn;
    
    int main()
    { 
    	int t;
    	cin >> t;
    	while(t--)
    	{ 
    		cin >> n;
    		sum = maxn = 0;
    		for(int i = 0;i < n;i++)
    			cin >> a[i];
    		for(int i = 1;i < n;i++)
    		{ 
    			b[i] = a[i] - a[i-1];	//存差分数组
    			sum += abs(b[i]);	//记录不修改的话的总和
    		}
    		for(int i = 0;i < n;i++)	//枚举每一个数，求修改的话减少的次数
    		{ 
    			if(!i)
    				maxn = max(maxn,abs(b[i+1]));	//如果是第一个数，减少的次数就是差分数组中他的下一个数的绝对值
    			else if(i == n-1)
    				maxn = max(maxn,abs(b[n-1]));	//如果是最后一个数，减少的次数就是差分数组中他自己的绝对值
    			else
    				maxn = max(maxn,abs(b[i+1])+abs(b[i])-abs(b[i+1]+b[i]));	//一般情况
    		}
    		cout << sum - maxn << endl;	//求得减少的最大次数maxn，用sum减去他就是答案
    	}
    
    	return 0;
    }

[B_Suffix Operations]: http://codeforces.com/contest/1453/problem/B
[b]: /images/20221120/4c64d74311424e4e9b892414850f5286.png