CCF CSP认证历年题目自练Day28

题目一

试题编号： 202109-1
试题名称： 数组推导
时间限制： 1.0s
内存限制： 512.0MB

样例1输入
6
0 0 5 5 10 10

样例1输出
30
15

样例2输入
7
10 20 30 40 50 60 75

样例2输出
285
285

题目分析（个人理解）

1. 我是这样理解的，第一行输入n个整数，第二行输入n个整数，这些整数单调不减，然后求这些整数的和就是求题目中sum的最大值，sum的最小值就是n个整数去重之后的和。（不理解我为啥这样写可以再多读题目自己理解）
2. 那真的很简单，我还是选择列表num存储，然后求和就是sum的最大值，去重之后求和就是sum的最小值，那么对于此题的去重我有两种方法，第一种对元素进行两两判断，如果不等就追加写入新列表，我在num[0]位插入0，然后
   for i in range(n):
   if num[i]!=num[i+1]:
   l.append(num[i+1])
   为什么要在num[0]填0，是因为原num的num[0]!=num[1]我追加写入的只有num[1]那么求和的时候会漏掉num[0]。
3. 第二种方法是判断列表num中不相同的元素，然后将不相同的写入新的列表，然后对新列表求和即是sum的最小值。
4. 上代码！！！

#方法一
n=int(input())
l=[]
num=list(map(int,input().split()))
num.insert(0,0)
for i in range(n):
    if num[i]!=num[i+1]:
        l.append(num[i+1])
print(sum(num))
print(sum(l))
1
2
3
4
5
6
7
8
9
10

#方法二
n=int(input())
l=[]
num=list(map(int,input().split()))
for i in num:
    if i not in l:
        l.append(i)
print(sum(num))
print(sum(l))
1
2
3
4
5
6
7
8
9

题目二

试题编号： 202109-2
试题名称： 非零段划分
时间限制： 1.0s
内存限制： 512.0MB

样例1输入
11
3 1 2 0 0 2 0 4 5 0 2

样例1输出
5

题目分析（个人理解）

1. 我们可以将想像成一个海岛问题，每一个超过海平面的小山顶就是一个非零段，p理解为海平面，现在就要求什么时候超过海平面的小山顶最多。
2. 现在设海面为0，岛屿为非零段，输入数组nums中的值代表当前下标位置的海拔高度。海平面从max(L)下降至1（海平面高度记为level），在海平面下降过程中，i处多了一个岛屿（非零段）当且仅当此时海平面高度<=i处海拔高度且[i-1],[i+1]处都为水（海拔小于海平面），i处减少了一个岛屿当且仅当此时海平面高度<=i处海拔高度且[i-1],[i+1]处都已经为岛屿。记数组island代表每个位置的目前状况(水或陆地)，即island[i]=0当且仅当nums[i]=level。
3. 将第二行输入的列表A[] 元素前后加0，表示都在海里，我选择用枚举函数enumerate()对列表，也就是岛屿的山顶标号，如果A的元素等于0就说明是海，不用记录，for id, num in enumerate(A):

#以下展示了使用 enumerate() 方法的实例：

>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 下标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

#for 循环使用 enumerate
>>> seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
...
0 one
1 two
2 three
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4. 我将每一个山顶的序号放入字典idx_dic{}的values里，将每一个山顶的高度放到keys里，字典的值是列表形式。
5. 上代码！！！

n = int(input())
# 数组前后补零
A = [0]+list(map(int, input().split()))+[0]
idx_dic = {}
maxnum = 0
for id, num in enumerate(A):
    # num是0不用记录
    if not num:
        continue
    maxnum = max(maxnum, num)
    if idx_dic.get(num) is None:
        idx_dic[num] = [id]
    else:
        idx_dic[num].append(id)
 
cnt, ans = 0, 0
island = [0]*(n+2)
for level in range(maxnum, 0, -1):
    if idx_dic.get(level) is None:
        continue
    for idx in idx_dic[level]:
        # 如果前后是陆地
        if island[idx-1] and island[idx+1]:
            cnt -= 1
        # 如果前后是水
        elif not island[idx-1] and not island[idx+1]:
            cnt += 1
        island[idx] = 1
    ans = max(ans, cnt)
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结

饭吃多了跑不动。