[数据结构与算法]Codeforces Round #688 (Div. 2) B. Suffix Operations(1400)

Codeforces Round #688 (Div. 2) B. Suffix Operations(1400)

$1400$构造捋一下，

• 题意：
  给你一个$n$个整数的数列$a$。你可以进行两种操作：
  $1、$后缀+$1$
  $2、$后缀 -$1$
  你可以改变其中的任何$1$个数为任何整数，也可以不变，然后进行上述操作。问最少需要操作几次，才能使所有数相同。
• 思路：
  看到这种前后缀操作次数的题目，第一想法是差分。我们可以想到，如果要所有数相等，那么差分数组除了第一个位置之外，后面的所有位置都应该为$0$。可以想到对后缀$a[i]$~$a[n]$进行操作的话,只会改变差分数组中$d[i]$ 的值，对于$i$前面和后面的位置都没有影响。那么我们操作的目的就是要让差分数组的除第一个位置之外的值，都为$0$。如果题目中没有说可以改变一个数的值的话，那么答案$O(n)$跑一遍即可求出。但是题目中还有一个改变操作，于是我们想到，如果减小$a[i]$的值，那么$d[i]$减小，$d[i+1]$增大；如果增加$a[i]$的值，那么$d[i]$增大，$d[i+1]$减小。我们改变值的目的肯定是要减少操作次数，那么只要顺着枚举每个位置，然后看如果改变这个位置的值能减少多少次操作，最后取大即可。

• code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
void cf(){
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++){
        sum+=abs(a[i]-a[i-1]);
    }
    int res=0;
    res=max(abs(a[2]-a[1]),abs(a[n-1]-a[n]));
    for(int i=2;i<=n-1;i++){
        if(a[i]-a[i-1]<0&&a[i+1]-a[i]<0||a[i]-a[i-1]>0&&a[i+1]-a[i]>0)continue;
        else{
            int x=min(abs(a[i]-a[i-1]),abs(a[i+1]-a[i]));
            res=max(res,x*2);
        }
    }
    cout<<sum-res<<endl;
} 
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖