第23次CCF CSP考试第一题

数组推导

题目描述

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输入

6
0 0 5 5 10 10

样例1输出

30
15

样例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输入

7
10 20 30 40 50 60 75

样例2输出

285
285

样例2解释

A=[10,20,30,40,50,60,75] 是唯一可能的取值，所以 sum 的最大、最小值均为 285。

子任务

50% 的测试数据满足数组 B 单调递增，即 0

全部的测试数据满足 n≤100 且数组 B 单调不降，即 0≤B1≤B2≤?≤Bn≤10^5。

---------------------------------------------------------------------

题解

一道简单的数学推理题目。由于Ｂ数组单调不减，因此只需要对相邻两个元素的值分两种情况讨论就行了。

当 B[i] > B[i - 1] 时，Ａ数组中必然出现了新的最大值，且下标为 i ；

当 B[i] = B[i - 1] 时，Ａ数组取最小值即可。

#include 
using namespace std;
const int N = 100010;

int n, mx, mn;
int b[N], ma[N], mi[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);　//读入最大值数组
    ma[1] = b[1], mi[1] = b[1];
    for (int i = 2; i <= n; i ++ )
    {
        if (b[i] > b[i - 1]) ma[i] = b[i], mi[i] = b[i];　//分类讨论
        else ma[i] = ma[i - 1], mi[i] = 0;
    }
    for (int i = 1; i <= n; i ++) mx += ma[i], mn += mi[i]; // 求和
    cout << mx << endl << mn;
    return 0;
}

非常easy