[常州市赛 2023] 奶牛农场

Luogu

IDLGB4217

Time1000ms

Memory512MB

DifficultyP2

贪心2023江苏Special Judge科创活动小学活动

小 X 是 CZ 市著名的农场主，他拥有着 CZ 市最大的奶牛农场。农场里有一排牛棚，一共 $n$ 个牛棚，从左到右依次编号为 $1,2,\cdots,n$ 。目前有些牛棚里住着奶牛，有些牛棚还是空的。每个奶牛有一个高度，其中第 $i$ 个牛棚里的奶牛的高度为 $H_i$，如果第 $i$ 个牛棚里没有奶牛的话，$H_i=0$，为了使小 X 的牛棚变得美观，他打算去市场上买一些奶牛放到空着的牛棚里（假设市场上能买到任意多个高度在 $1$ 到 $10^9$ 之间的任意正整数的奶牛），使得每个牛棚里都有一头奶牛，并且高度从左往右严格递增。请你告诉小 X 是否能让他的牛棚变得美观，如果可以请给出一个任意合法的方案。 ## Input 第一行 $1$ 个正整数 $n$，表示牛棚个数。第二行 $n$ 个非负整数 $H_i$，如果 $H_i=0$ 说明第 $i$ 个牛棚是空的，否则说明第 $i$ 个牛棚里面有一个高度为 $H_i$ 的奶牛。 ## Output 第一行输出一个字符串 ```YES``` 或 ```NO```。如果让他的牛棚变得美观，则输出 ```YES```，否则输出 ```NO```。如果第一行输出 ```YES```，再输出第二行 $n$ 个正整数 $1\leq H'_i\leq 10^9$ ，你需要保证对所有 $1\leq i\leq n-1$ 满足 $H'_i<H'_{i+1}$ ，并且如果 $H'_i>0$ ，那么 $H'_i=H_i$ ，如果有多种合法的方案，输出任意一种即可。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/674>。数据为民间数据。 ## Note ### 样例 $\textbf 3$ 解释因为高度是正整数，还要严格递增，所以第 $4$ 头奶牛的高度必须 $\geq 2$ 。所以不存在满足题目条件的方案。 ### 样例 $\textbf 4$ 解释因为买不到高度为 $>10^9$ 的奶牛，所以不存在满足题目条件的方案。 ### 数据范围 | 测试点编号 | $n$ | $H_i$ | | :---: | :---: | :---: | | $1\sim5$ | $1\leq n\leq 5$ | $0\leq H_i\leq10$ | | $6\sim10$ | $1\leq n\leq 10^5$ | $0\leq H_i\leq 10^9$ |

Samples

Input #1

3
0 0 0

Output #1

YES
4 5 6

Input #2

4
0 2 0 4

Output #2

YES
1 2 3 4

Input #3

4
0 0 0 2

Output #3

NO

Input #4

2
1000000000 0

Output #4

NO

API Response (JSON)

{
  "problem": {
    "name": "[常州市赛 2023] 奶牛农场",
    "description": {
      "content": "小 X 是 CZ 市著名的农场主，他拥有着 CZ 市最大的奶牛农场。农场里有一排牛棚，一共 $n$ 个牛棚，从左到右依次编号为 $1,2,\\cdots,n$ 。目前有些牛棚里住着奶牛，有些牛棚还是空的。 每个奶牛有一个高度，其中第 $i$ 个牛棚里的奶牛的高度为 $H_i$，如果第 $i$ 个牛棚里没有奶牛的话，$H_i=0$，为了使小 X 的牛棚变得美观，他打算去市场上买一些奶牛放到空着的牛棚",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4217"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 是 CZ 市著名的农场主，他拥有着 CZ 市最大的奶牛农场。农场里有一排牛棚，一共 $n$ 个牛棚，从左到右依次编号为 $1,2,\\cdots,n$ 。目前有些牛棚里住着奶牛，有些牛棚还是空的。\n\n每个奶牛有一个高度，其中第 $i$ 个牛棚里的奶牛的高度为 $H_i$，如果第 $i$ 个牛棚里没有奶牛的话，$H_i=0$，为了使小 X 的牛棚变得美观，他打算去市场上买一些奶牛放到空着的牛棚...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments