CF-1453B

题意: 一个数组，每次可以选择一个后缀，将其加一或者减一，开始的时候可以免费改变一个数的数值，判断让所有数字相等所需要的最小操作数。

题解: 注意它的操作，每次改变的是一个后缀，不是自己随意选择子区间(开始读错题，一直没看懂.....)，首先我们不考虑免费改变的那次，很明显，如果让所有数相同，肯定要都等于第一个，因为每次改变的是一个后缀，如果你最后变成的不是第一个数，那么你要变成的呢个数的前面的数一定会影响后面数，而且，每次改变后缀，那么后面的各个数之间的差值一定是不变的，求出开始值，然后判断要改变哪一个位置的数，求出最小值即可。

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int N=2e5+10;

const ll mod=1e9+7;

ll cnt;

ll a[N];

signed main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll t;cin>>t;

  while(t--){

    ll n;cin>>n;

    ll sum=0,ans;

    for(ll i=1;i<=n;i++){

       cin>>a[i];

       if(i>=2)  sum+=abs(a[i]-a[i-1]);//求出不用免费的那一次的最小值

    }

    ans=sum;

    for(ll i=2;i<=n-1;i++){

       ans=min(ans,sum-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1]));//改变该位置的值，会影响前后两个数

    }

    ans=min(ans,sum-abs(a[2]-a[1]));//第一个数和最后一个数特判一下

    ans=min(ans,sum-abs(a[n]-a[n-1]));

    cout<<ans<<endl;

  }

}

巴特西

CF-1453B

最新文章

热门文章