小美的代金券要过期啦

[编程题]小美的代金券要过期啦

热度指数：2871 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

外卖节即将过去了，小美还有很代金券没有消费掉，美团面向小美这样的用户推出了一个新的活动，即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排，小美可以进行任意多次如下操作：

如果存在相邻的两个代金券金额相等,设其面额为x，小美可以使用这两张代金券换一张面额为x+1的代金券，并将其仍放在原来两张券的位置上，每进行一次这样的操作，小美就可以获得1元可以无限期使用的奖励金。

小美觉得奖励金可太香了，因此她想获得尽可能多的奖励金，请问她最多可以获得多少奖励金。

输入描述:

输入第一行仅包含一个正整数n，表示小美拥有的代金券数量。(1<=n<=500)
输入第二行包含n个正整数，每个整数x表示一张代金券的面额，同时这也是系统排出的代金券顺序。(1<=x<=100)

输出描述:

输出仅包含一个整数，表示小美最多可以获得的奖励金数量。

示例1

输入

5
1 1 1 1 1

输出

说明

{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}

算法知识视频讲解

Python

已注销

直接就在原数组上合，很暴力

n = int(input())
values = [int(x) for x in input().split()]
count = 0
i = 1
while i < len(values):
    if values[i] == values[i-1]:
        values.pop(i-1)
        values[i-1] = values[i-1] + 1
        count += 1
        i = 1
    else:
        i += 1
print(count)

然后发现53ms............

发表于 2023-04-14 02:07:27 回复(0)

Python

顺利上岸吧求求了

n=int(input())
an=list(map(int, input().strip().split()))
stack=[]
res=0
for num in an:
    if not stack&nbs***bsp;stack[-1]!=num:
        stack.append(num)
    else:
        while stack and num==stack[-1]:
            stack.pop()
            num+=1
            res+=1
            
        stack.append(num)

print(res)

利用栈，每一个数x和栈顶元素相同则弹出，将x=x+1继续与栈顶元素比较，直到不等时入栈。
每弹出一次结果加一。

发表于 2022-03-25 17:35:11 回复(1)

Python

Ivan_2021

num = int(input())
stack1 = list(map(int, input().split()))

stack2 = []
count = 0
while stack1:
    temp = stack1.pop()
    while stack1&nbs***bsp;stack2:
        if stack1 and stack1[-1] == temp:
            temp += 1
            count += 1
            stack1.pop()
        elif stack2 and stack2[-1] == temp:
            temp += 1
            count += 1
            stack2.pop()
        else:
            stack2.append(temp)
            break
print(count)

奇怪的能过的python代码。

发表于 2021-09-29 21:25:28 回复(0)