奶牛农场
描述
小 X 是 CZ 市著名的农场主,他拥有着 CZ 市最大的奶牛农场。农场里有一排牛棚,一共n 个牛棚,从左到右依次编号为 1,2,….,n。目前有些牛棚里住着奶牛,有些牛棚还是空的。
每个奶牛有一个高度,其中第 i 个牛棚里的奶牛的高度为 H[i],如果第 i 个牛棚里没有奶牛的话则 H[i]=0,为了使小 X 的牛棚变得美观,他打算去市场上买一些奶牛放到空着的牛棚里(假设市场上能买到任意多头高度在 1 到 10^9 之间的任意正整数的奶牛),使得每个牛棚里都有一头奶牛,并且高度从左往右严格递增。
请你告诉小 X 是否能让他的牛棚变得美观,如果可以请给出一个任意合法的方案。
输入描述
第一行 1 个正整数 n,表示牛棚个数。
第二行 n 个非负整数 H[i],如果 H[i]=0 说明第 i 个牛棚是空的,否则说明第 i 个牛棚里面有一头高度为 H[i]的奶牛。
输出描述
第一行输出一个字符串”YES”或”NO”。如果能让他的牛棚变得美观,则输出”YES”,否则输出”NO”。(均不包含引号)
如果第一行输出”YES”,再输出第二行 n 个正整数 1<=H’[i]<=10^9,你需要保证对所有1<=i<=n-1 满足 H’[i]<H’[i+1],并且如果 H[i]>0,那么 H’[i]=H[i],如果有多种合法的方案,输出任意一种即可。
用例输入 1
3
0 0 0
用例输出 1
YES
4 5 6
用例输入 2
4
0 2 0 4
用例输出 2
YES
1 2 3 4
用例输入 3
4
0 0 0 2
用例输出 3
NO
用例输入 4
2
1000000000 0
用例输出 4
NO
提示
【样例 3 解释】
因为高度是正整数,还要严格递增,所以第 4 头奶牛的高度必须>=4。所以不存在满足题目条件的方案。
【数据范围】
本题共有 9 个测试点,每个测试点 10 分。
对于测试点 1-5 :1<=n<=5,0<=H[i]<=10。
对于测试点 6-9:1<=n<=10^5,0<=H[i]<=10^9。
信息
- ID
- 2688
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 44
- 已通过
- 6
- 通过率
- 14%
- 上传者
相关
在下列比赛中: