CCF CSP 2021-9-1 数组推导 C语言100分

CCF CSP 2021-9-1 数组推导 C语言100分

CCF CSP 2021-9-1 数组推导C语言100分

数组推导 代码长度363B C语言 正确 100分 耗时15ms 运行内存2.511MB 2021-11-04完成

应该会慢慢更新，0算法基础极限挑战今年12月得CSP。坚持每天一道

题目描述
A1,A2,…,An是一个由 n个自然数（即非负整数）组成的数组。在此基础上，我们用数组B1…Bn表示A的前缀最大值。
B i = m a x { A 1 , A 2 , . . . , A i } Bi=max{A1,A2,…,Ai}
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。

子任务
1、50% 的测试数据满足数组 B 单调递增，即 0 < B1 < B2 < … < Bn < 10^5；
2、全部的测试数据满足 n ≤ 100 且数组 B 单调不降，即 0 ≤ B1 ≤ B2 ≤ … ≤ Bn ≤ 10^5。
子任务说明什么：满足第一条得70分，满足第二条得100分，一般要注意第二条容易超时，所以要简化算法。

#include
int main()
{
	int n,i;
	int max=0, min=0;
	scanf("%d", &n);
	int num[n];
	for(i=0;inum[i-1])
		{
			max+=num[i]; 
			min+=num[i]; 
		};
		if (num[i]==num[i-1])
		{
			max+=num[i]; 
			min+=0;
		};
	};
	printf("%dn", max);
	printf("%d", min);
	return 0;
}