首页 > 试题广场 >

获得最多的奖金

[编程题]获得最多的奖金
  • 热度指数：27815 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”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越南盾。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:40:44
题目难度：二星考察点：双指针 方法1：暴力、前缀和 分析：我们按照题意进行计算，枚举第一刀下标i和第二刀的下标j即可，然后判断区间[1, i]和区间[j,n]的和是不是相等，如果相等记录答案，取最大值即可。在计算区间和的时候要注意的是需要提前预处理一下前缀和，要不然直接计算区间和的话会使得时间复杂 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 446644
发表于 2022-03-23 14:33:21
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.ne 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 为此怀念
发表于 2022-09-14 17:20:22
while True:     try:         n=int(input())         ls=list(map(i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 名字来我身边
发表于 2022-09-01 08:46:15
#include "bits/stdc++.h" using namespace std; int main(){     int n;     cin>>n;          vector& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 右神
发表于 2022-08-14 22:46:38
import java.util.*; public class Main{     public static void main(String[] args){    展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 野蛮的河老师在干饭
发表于 2023-03-11 15:52:51
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new S 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 黄金国不会做幻崩访问梦
发表于 2022-09-27 10:29:53
自己想的，事件空间复杂度都有点高了，暴力解法：用两个数组存前、后遍历的和，再遍历判断是否有相等的 public class Main {     public static void main(S 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客499819205号
发表于 2021-10-21 14:43:28
#include<iostream> #include<vector> using namespace std; int main() { int n; while(cin >>n) { vector<int> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 贪吃的迪恩顶呱呱
发表于 2024-05-01 15:03:35
使用双指针从两端遍历数组，根据遍历的情况决定往左边加数还是往右边加数，遍历完的条件是两个指针相遇，至于中间分一组这个要求，可以直接不做处理 #include <algorithm> #include <iostream> #include <vector> usi 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 求捞捞的小邹
发表于 2023-10-28 09:32:43
#include <stdio.h> int main() { long n; scanf("%ld",&n); long data[n]; for(long i=0;i<n;i++) scanf(&qu 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 快手 数组 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 2019 Java工程师
上传者：小小
难度：
85条回答 12750浏览

热门推荐

通过挑战的用户

查看代码

相关试题

获得最多的奖金

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号