正題

題目鏈接:https://www.luogu.com.cn/problem/P4552

---

題目大意

給出$n$個數(shù)，每次可以選擇一個區(qū)間加一或減一，求最少操作使得所有數(shù)相等，并且求可能的最終序列個數(shù)。

---

解題思路

在差分數(shù)組上操作，那么操作變?yōu)閷⒉罘謹?shù)組上一個數(shù)$+1$且一個數(shù)$?1$（當然當$l=1$或$r=n$時就是只改變一個數(shù)）。所以最少操作數(shù)就是正數(shù)的和和負數(shù)的絕對值和的最大值。

序列種數(shù)，假設正數(shù)和$z$大于負數(shù)和$f$，那么其實對于$f～z$這個范圍內的我們都可以選擇是讓$l=1$來修改或者$r=n$來修改，所以個數(shù)和就是$abs(f?z)+1$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll n,a[1100000],z,f; int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);ll x=a[i]-a[i-1];if(i==1)continue;z+=(x>0)*x;f-=(x<0)*x;}printf("%lld\n%lld",max(z,f),abs(z-f)+1); }

總結

以上是生活随笔為你收集整理的P4552-[Poetize6]IncDec Sequence【差分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。