个算法题想了好久没思路,求指点

2020-07-27 17:18:54 +08:00
 penguinhlxhands

射击训练,需要给每个士兵发子弹,发子弹的个数规则是根据士兵的训练成绩给定的,传入士兵的训练成绩,要求相邻士兵中,成绩好的士兵的子弹数必须更多,每个士兵至少分配一个子弹。

输入描述:

输入每个士兵的训练成绩,如 1,2,3,代表 3 位士兵的成绩分别为 1,2,3

输出描述:

最少分配的子弹数

示例 1:

输入:1,2,2

输出:4

1574 次点击
所在节点    Python
4 条回复
AlisaDestiny
2020-07-27 21:35:49 +08:00
这个就是求数据的极值点,最小值处的值都是 1,最大值处的值是 n = max(到左极值距离,到右极值距离),距离远的一侧从最小值处到最大值处需要的子弹数是 sum(1..n),另一侧是 sum(1..到极大值距离-1)
AlisaDestiny
2020-07-27 21:38:38 +08:00
需要的子弹总数就是将各个区段的和值相加。
nthhdy
2020-07-27 22:00:11 +08:00
如果相邻的分数相同,应该是没有约束的
warush
2020-07-28 01:51:24 +08:00
这不就是 leetcode 上的 candy,从左往右便利一下给最低的子弹,然后再从有往左边遍历一遍

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/693514

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX