| 试题编号： | 202109-1 | | 试题名称： | 数组推导 | | 时间限制： | 1.0s | | 内存限制： | 512.0MB | | 问题描述： | 题目描述 A1,A2,?,An 是一个由 n 个自然数（即非负整数）组成的数组。在此基础上，我们用数组 B1?Bn 表示 A 的前缀最大值。
Bi=max{A1,A2,?,Ai} 如上所示，Bi 定义为数组 A 中前 i 个数的最大值。
根据该定义易知 A1=B1，且随着 i 的增大，Bi 单调不降。
此外，我们用 sum=A1+A2+?+An 表示数组 A 中 n 个数的总和。 现已知数组 B，我们想要根据 B 的值来反推数组 A。
显然，对于给定的 B，A 的取值可能并不唯一。
试计算，在数组 A 所有可能的取值情况中，sum 的最大值和最小值分别是多少？ 输入格式 从标准输入读入数据。 输入的第一行包含一个正整数 n。 输入的第二行包含 n 个用空格分隔的自然数 B1,B2,?,Bn。 输出格式 输出到标准输出。 输出共两行。 第一行输出一个整数，表示 sum 的最大值。 第二行输出一个整数，表示 sum 的最小值。 样例1输入
样例1输出
样例1解释 数组 A 的可能取值包括但不限于以下三种情况。 情况一：A=[0,0,5,5,10,10] 情况二：A=[0,0,5,3,10,4] 情况三：A=[0,0,5,0,10,0] 其中第一种情况 sum=30 为最大值，第三种情况 sum=15 为最小值。 样例2输入
样例2输出
样例2解释 A=[10,20,30,40,50,60,75] 是唯一可能的取值，所以 sum 的最大、最小值均为 285。 子任务 50% 的测试数据满足数组 B 单调递增，即 0<B1<B2<?<Bn<105； 全部的测试数据满足 n≤100 且数组 B 单调不降，即 0≤B1≤B2≤?≤Bn≤105。 |
2. 问题分析：
经过读题分析，当
A
i
=
B
i
A_i=B_i
Ai?=Bi?时，
A
i
A_i
Ai?始终为表示
A
A
A 的前缀最大值，即数组
A
A
A 中前
i
i
i个数的最大值，此时
s
u
m
sum
sum为最大值；因为数组
B
B
B 单调不降，当数组
B
B
B连续值第一次不相等时，此时
A
i
=
B
i
A_i=B_i
Ai?=Bi?，连续值相等时从第二次开始均满足
A
i
=
0
A_i=0
Ai?=0，此时
s
u
m
sum
sum为最小值；
3. C++语言程序实现:
#include <iostream>
using namespace std;
int main()
{
int n,Bi,Bj,sum_max=0,sum_min=0;
scanf("%d%d",&n,&Bi);
sum_max=Bi;
sum_min=Bi;
for (int i=1;i<n ;i++ )
{
scanf("%d",&Bj);
sum_max+=Bj;
if (Bi!=Bj)
{
sum_min+=Bj;
}
Bi=Bj;
}
printf("%d\n%d\n",sum_max,sum_min);
return 0;
}
4. Python语言程序实现:
n=int(input())
B=[int(i) for i in input().split()]
sum_max=sum_min=Bi=B[0]
for Bj in B[1:]:
sum_max+=Bj
if Bi!=Bj:
sum_min+=Bj
Bi=Bj
print("{}\n{}".format(sum_max,sum_min))
|