首页 > 试题广场 >

获得最多的奖金

[编程题]获得最多的奖金
  • 热度指数:27554 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
小明在越南旅游,参加了当地的娱乐活动。小明运气很好,拿到了大奖, 到了最后的拿奖金环节。小明发现桌子上放着一列红包,每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀,将这一列红包“切”成3组,并且第一组的奖金之和等于最后一组奖金和(允许任意一组的红包集合是空)。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少,你能帮他算算吗。

举例解释:桌子上放了红包  1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀,将红包分成3组 [1, 2, 3, 4]   [7]   [10],其中第一组奖金之和=第三组奖金之和=10,所以小明可以拿到10越南盾。

数据范围:红包数量满足 ,红包金额满足

输入描述:
第一行包含一个正整数n,表示有多少个红包。

第二行包含n个正整数d[i],表示每个红包包含的奖金数额。


输出描述:
小明可以拿到的总奖金
示例1

输入

5
1 3 1 1 4

输出

5

说明

[1,3,1]  [ ]   [1,4] ,其中第一组奖金和是5,等于第三组奖金和。所以小明可以拿到5越南盾 
示例2

输入

5
1 3 2 1 4

输出

4

说明

[1,3]   [2,1]  [4],小明可以拿到4越南盾 
示例3

输入

3
4 1 2

输出

0

说明

[ ]  [4, 1, 2] [ ] ,小明没办法,为了保证第一组第三组相等,只能都分成空的。所以小明只能拿到0越南盾。 
while True:
    try:
        n = int(input())
        lis = list(map(int,input().split(' ')))
        Money_gain = 0

        right = n-1
        left = 0

        sum1 = lis[left]
        sum2 = lis[right]

        while left < right:
            if sum1 == sum2:
                Money_gain = max(Money_gain,sum1)
                left += 1
                right -= 1
                sum1 += lis[left]
                sum2 += lis[right]
            elif sum1 > sum2 :
                right -= 1
                sum2 += lis[right]
            else:
                left += 1
                sum1 += lis[left] 
        print(Money_gain)     
    except:
        break
        
发表于 2023-06-12 00:21:00 回复(0)
n = int(input())
d = list(map(int, input().split()))
a = []
s1 = []
s2 = []
for j in range(n):
    for i in range(j + 1):
        s1.append(sum(d[:i]))
        s2.append(sum(d[j:]))
        for z in range(len(s1)):
            if s1[z] == s2[z]:
                a.append(s1[z])
            else:
                a.append(0)
print(max(a))
运行超时,实在不知道咋搞了,等评论区吧

发表于 2022-10-21 16:13:27 回复(1)