[CSP-X2020 山东] 分糖果

Luogu
IDLGB4091
Time1000ms
Memory128MB
DifficultyP3
模拟贪心2020山东排序CSP-X 小学组
每个孩子只能看见与自己相邻的 $2$ 个孩子(左边的和右边的)的情况,只会关心相邻的且比自己评分低的同学的糖果数(如果相邻 $2$ 个孩子的评分相等,则不关心)。为保证公平,相邻的孩子中,评分高的孩子必须获得更多的糖果(如果左右相邻 $2$ 个孩子的评分相等,则不关心,即分最少的糖果 $1$ 个)。同时,为鼓励孩子的积极性,每个孩子至少都能拿到 $1$ 个糖果。现在需要你帮助老师来分发糖果,问怎么分配才能使要准备的糖果数最少?计算出需要的最少糖果数。 ## Input 输入有二行,第一行一个正整数 $n$ 表示孩子的个数。 第二行 $n$ 个非负整数,相邻的数用空格隔开,分别表示孩子的表现评分。 ## Output 一个整数,表示最少需要准备的糖果数。 [samples] ## Background 老师组织一群孩子围成一个圈进行游戏,游戏结束后老师会根据每个孩子的表现进行评分并给予糖果奖励。 ## Note 【数据范围】 对于 $40\%$ 的数据,$1\leq n\leq 100$; 对于 $100\%$ 的数据,$1\leq n\leq 10^5$; 所有评分都是 $0$ 到 $100$ 之间的一个整数。 【样例解释】 样例一,分别分配 $2,3,1$ 的糖果,所以最少需要 $6$ 个糖果。 样例二,分别分配 $1,2,1,2$ 的糖果,所以最少需要 $6$ 个糖果。
Samples
Input #1
3
1 2 0
Output #1
6
Input #2
4
2 3 3 3
Output #2
6
API Response (JSON)
{
  "problem": {
    "name": "[CSP-X2020 山东] 分糖果",
    "description": {
      "content": "每个孩子只能看见与自己相邻的 $2$ 个孩子(左边的和右边的)的情况,只会关心相邻的且比自己评分低的同学的糖果数(如果相邻 $2$ 个孩子的评分相等,则不关心)。为保证公平,相邻的孩子中,评分高的孩子必须获得更多的糖果(如果左右相邻 $2$ 个孩子的评分相等,则不关心,即分最少的糖果 $1$ 个)。同时,为鼓励孩子的积极性,每个孩子至少都能拿到 $1$ 个糖果。现在需要你帮助老师来分发糖果,问怎么",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4091"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "每个孩子只能看见与自己相邻的 $2$ 个孩子(左边的和右边的)的情况,只会关心相邻的且比自己评分低的同学的糖果数(如果相邻 $2$ 个孩子的评分相等,则不关心)。为保证公平,相邻的孩子中,评分高的孩子必须获得更多的糖果(如果左右相邻 $2$ 个孩子的评分相等,则不关心,即分最少的糖果 $1$ 个)。同时,为鼓励孩子的积极性,每个孩子至少都能拿到 $1$ 个糖果。现在需要你帮助老师来分发糖果,问怎么...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments