题解：B4217 [常州市程序设计小能手 2023] 奶牛农场

yyycj · 2025-03-09 13:28:51 · 题解

题目简述

给你一个整数序列 H，如果 H_{i}=0，则可以将 H_{i} 改为 [1,10^{9}] 中的一个数。

判断是否能让这个 H 单调上升，如果可以输出 YES 和任意一种满足的情况；反之输出 NO。

主要思路

输出 NO 的情况比较显而易见，满足以下一条即可（以下条件都建立在 H_{i} \neq 0 的情况）：

• 对于每个 j \in [1,i)，H_{i} \le H_{j}。

以上条件都不满足则一定输出 YES，由于任意一种满足条件的序列都可以，所以对于 H_{i} = 0，H_{i} \to H_{i - 1} + 1 即可。

AC Code

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

namespace IO {
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    #define pc putchar
    #define gc getchar
    template<typename T> void read(T &x) { int f = 1; x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }x *= f; }
    template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
    template<typename T> void print(T x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
    template<typename T, typename ...Args> void print(T &x, Args &...args) { print(x); pc(' '); print(args...); }
    inline void readstr(string& x) { x.clear(); char ch = gc(); while (isspace(ch)) ch = gc(); while (!isspace(ch) && ch != EOF) { x.push_back(ch); ch = gc(); } }
    inline void printstr(char* x) { for (int i = 0; i < (int)strlen(x); i++) pc(x[i]); }
    inline void printstr(string& x) { for (auto i = x.begin(); i != x.end(); i++) pc(*i); }
};
using namespace IO;

#define OUT 0
#define MAMBA return
typedef long long ll;
typedef long double db;
const int N = 1e5 + 10;
const int INT_INF = 0x3f3f3f3f;
int man();int main(){MAMBA man();}
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
inline ll _abs(ll a) { if (a < 0) return -a; return a; }
inline ll _pow(ll a, ll b) { ll x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------
int h[N];
// ----------------------------

int man() {
    int n, last = -1; read(n);
    for (int i = 1; i <= n; i++) {
        read(h[i]);
        if (h[i] != 0 && (h[i] < i || h[i] > 1000000000 - (n - i) || h[i] <= last)) {
            printstr("NO");
            MAMBA OUT;
        }
        if (h[i] != 0) last = h[i];
    }
    // ----------------------------
    printstr("YES\n");
    for (int i = 1; i <= n; i++) {
        if (h[i] == 0) h[i] = h[i - 1] + 1;
        print(h[i]);
        pc(' ');
    }
    MAMBA OUT;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/