5526. 平衡細菌
題意
給定一個序列 ( a i ) (a_i) (ai?)，每次操作可以選擇一個位置 (p)，令從 ( a p ) (a_p) (ap?) 開始的每個數都加上一個以 (1) 或者 (-1) 為公差的從 ( 1 / ? 1 ) (1 / -1) (1/?1) 開始的等差數列。求最小化讓序列歸零的操作次數。
解題思路
這是一道差分模板題，我們從差分角度觀察操作的本質：
- 給一段區間加上： ( 1 , 2 , 3 , 4 , 5 … ) (1, 2, 3, 4, 5 \ldots) (1,2,3,4,5…)
- 在一階差分數組上： ( 1 , 1 , 1 , 1 , 1 … ) (1, 1, 1, 1, 1 \ldots) (1,1,1,1,1…)
- 在二階差分數組上： ( 1 , 0 , 0 , 0 , 0 … ) (1, 0, 0, 0, 0 \ldots) (1,0,0,0,0…)
所以每次修改的本質實際上是在二階差分數組上 (+1) 或者 (-1)。要讓原序列變成 (0) 序列，等價于要讓它的二階差分數組變成 (0) 序列，因此答案就是二階差分數組中所有數的絕對值之和。
欽定： d i = a i ? a i ? 1 , d d i = d i ? d i ? 1 d_i = a_i - a_{i - 1}, dd_i = d_i - d_{i - 1} di?=ai??ai?1?,ddi?=di??di?1?
ans = ∑ i = 1 n ∣ d d i ∣ \text{ans} = \sum_{i = 1}^{n} |dd_i| ans=i=1∑n?∣ddi?∣
AC Code
// Problem: 平衡細菌
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5529/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
typedef long long ll; // 確保 ll 在使用前被定義
using namespace std;
using i64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= n;++i)
#define int long long
#define pii pair<int,int>
#define In \ll n; \std::cin >> n;\
const int mod = 1e9 + 7, N = 1e7;void solve(){In; vector<i64> a(n + 1), d(n + 1), dd(n + 1);for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= n; i ++) d[i] = a[i] - a[i - 1];for(int i = 1; i <= n; i ++) dd[i] = d[i] - d[i - 1];i64 ans = 0;for(int i = 1; i <= n; i ++) ans += abs(dd[i]);cout << ans << '\n';
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);ll T = 1;//std::cin >> T;for(int i = 1; i <= T; ++i) solve();
}
