首页 > 试题广场 >

糖果游戏

[编程题]糖果游戏
  • 热度指数：1445 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明和小红都很喜欢吃糖果，今天他们一起玩一个糖果游戏。他们将装有不同数量的透明糖果盒子摆放成一个环，现在两人依次选择糖果盒子，小明先拿，且小明第一次挑选可以选择环中任意一个糖果盒子，将环分割成一列有首尾的序列，之后两人每次选择时只能从剩余的糖果盒子序列的行首或者行尾挑选，直到两人将糖果盒子全部拿完，最后糖果多的为胜者。假设两人都希望自己是最后的赢家，且糖果的总数是奇数，现给定一个糖果的环，用一个数组表示环中的各糖果盒子中糖果的数量，数组首尾相连成环，元素个数为N。请输出胜利者比失败者至少多拿多少糖果。

输入描述:
第一行：N
第2至N+1行：每行一个数，代表糖果数


输出描述:
一个数，请输出胜利者比失败者多拿多少糖果
示例1

输入

4 
1
55
41
2

输出

15

说明

小明先选择55，此时环从55处断开，变为序列[41, 2, 1]
小红选择行首的41，此时剩余的序列为[2, 1]
小明选择行首的2，此时剩余的序列为[1]
小红选择剩余的1。
此时小明胜利，比小红多15个糖果
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 小米集团 搜狗 2019 Java工程师
来自：搜狗2019秋招研究员...
上传者：小小
难度：
0条回答 6044浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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