A23495. 奶牛农场小X是CZ市著名的农场主，他拥有着CZ市最大的奶牛农场。农场里有一排牛棚，一共n个牛棚，从左到右依次编号为1,2,…,n。目前有些牛棚里住着奶牛，有些牛棚还是空的。每个奶牛有一个高度，其中第i个牛棚里的奶牛的高度为H[i]，如果第i个牛棚里没有奶牛的话H[i]=0。为了使小X的牛棚变得美观，他打算去市场上买一些奶牛放到空着的牛棚里（假设市场上能买到任意多个高度在1到10^9之间的任意正整…
填空题
中等
知识点
题目描述
奶牛农场
小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样例输入2
4
0 2 0 4样例输入3
4
0 0 0 2样例输入4
2
1000000000 0样例输出1
YES
4 5 6样例输出2
YES
1 2 3 4样例输出3
NO样例输出4
NO提示
样例3解释
因为高度是正整数，还要严格递增，所以第4头奶牛的高度必须>=4。所以不存在满足题目条件的方案。
样例4解释
因为买不到高度>10^9的奶牛，所以不存在满足题目条件的方案。
数据范围
对于测试点1-5：1<=n<=5,0<=H[i]<=10。 对于测试点6-9：1<=n<=10^5,0<=H[i]<=10^9。
参考答案
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> H(n);
for (int i = 0; i < n; ++i) {
cin >> H[i];
}
// 从左到右处理非0元素，确保递增
for (int i = 1; i < n; ++i) {
if (H[i] != 0 && H[i-1] != 0 && H[i] <= H[i-1]) {
cout << "NO" << endl;
return 0;
}
}
// 填充左侧0（以右侧非0为约束）
for (int i = n-2; i >= 0; --i) {
if (H[i] == 0) {
if (H[i+1] == 0) continue; // 右侧也是0，先不处理
H[i] = H[i+1] - 1;
if (H[i] < 1) { // 必须是正整数
cout << "NO" << endl;
return 0;
}
}
}
// 填充右侧0（以左侧非0为约束）
for (int i = 1; i < n; ++i) {
if (H[i] == 0) {
H[i] = H[i-1] + 1;
if (H[i] > 1e9) { // 超过最大值
cout << "NO" << endl;
return 0;
}
}
}
// 最终检查是否严格递增
for (int i = 1; i < n; ++i) {
if (H[i] <= H[i-1]) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
for (int num : H) {
cout << num << " ";
}
cout << endl;
return 0;
}
上一题
下一题