AcWing-蓝桥杯集训每日一题20255526.-平衡细菌
目录
AcWing 蓝桥杯集训·每日一题2025·5526. 平衡细菌
题意
给定一个序列
( a i ) (a_i)
(
a
i
) ，每次操作可以选择一个位置 (p)，令从
( a p ) (a_p)
(
a
p
) 开始的每个数都加上一个以 (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}
d
i
=
a
i
−
a
i
−
1
,
d
d
i
=
d
i
−
d
i
−
1
ans
∑ i
1 n ∣ d d i ∣ \text{ans} = \sum_{i = 1}^{n} |dd_i|
ans
=
i
=
1
∑
n
∣
d
d
i
∣
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();
}