深圳工厂网站建设公司,html 做网站案例简单,家具网站建设案例,it外包公司工资一般多少5526. 平衡细菌
题意
给定一个序列 ( a i ) (a_i) (ai)#xff0c;每次操作可以选择一个位置 (p)#xff0c;令从 ( a p ) (a_p) (ap) 开始的每个数都加上一个以 (1) 或者 (-1) 为公差的从 ( 1 / − 1 ) (1 / -1) (1/−1) 开始的等差数列。求最小化让序列归零的操作…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} diai−ai−1,ddidi−di−1 ans ∑ i 1 n ∣ d d i ∣ \text{ans} \sum_{i 1}^{n} |dd_i| ansi1∑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)#includebits/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 pairint,int
#define In \ll n; \std::cin n;\const int mod 1e9 7, N 1e7;void solve(){In; vectori64 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();
}
