CF1326B - Maximums 题解

因为 \(x_i=\max\{0,a_1\sim a_{i-1}\}\),所以当 \(i=1\) 时,\(x_i=0\)。

又因为 \(b_i=a_i-x_i\),所以 \(b_1=a_1-x_1=a_1-0=a_1\)。

以此类推,\(b_2=a_2-x_2=a_2-\max\{0,a_1\sim a_{2-1}\}=a_2-\max\{0,a_1\}\),\(b_3=a_3-x_3=a_3-\max\{0,a_1\sim a_{3-1}\}=a_3-\max\{0,a_1\sim a_2\}\),……

因为数组 \(b\) 的值已知,所以只需维护 \(\max\{a_1\sim a_{i-1}\}\) 的值即可得到数组 \(a\) 的值。

Code:

const int maxN=200005;
int n,b[maxN],a[maxN];
int main() {
	cin>>n;
	for (int i=1;i<=n;i++) cin>>b[i];
	a[1]=b[1];
	int maxx=max(a[1],0);
	for (int i=2;i<=n;i++) a[i]=maxx+b[i],maxx=max(0,max(maxx,a[i]));
	for (int i=1;i<=n;i++) cout<<a[i]<<' ';
}
上一篇:ubuntu 安装 pytesseract 模块进行图片内容识别


下一篇:Java 集合系列之一:JCF集合框架概述