当前位置：首页 > news >正文

[玄学]JZOJ 5811 简单的填数

news 来源：原创 2024/4/29 10:03:04

Description

Input

第一行一个数 n，表示序列的长度。
第二行 n 个整数，第 i 个整数表示 ai，如果 ai = 0，则表示这个位置没有填数。

Output

如果不存在合法的填数方案，则输出 −1；否则第一行输出一个整数，表示最大的 an；第二行 n 个正整数，第 i 个数表示完成填数后的序列的第 i 个元素。如果有多组合法的解，输出任意一组

Sample Input

【样例 1 输入】
7
0 1 0 0 0 3 0
【样例 2 输入】
4
0 0 0 3

Sample Output

【样例 1 输出】
3
1 1 2 2 3 3 3
【样例 2 输出】
-1

Data Constraint

对于 30% 的数据，n ≤ 1000；
对于另外 30% 的数据，数据保证随机生成；
对于 100% 的数据，2 ≤ n ≤ 2 × 10^5 , 0 ≤ ai ≤ 10^5。

分析

这道题我们可以维护二元组（x表示值，y表示之前这个值出现的最长长度）

两个二元组，up和down，up表示x尽可能大，down相反

那么显然遇到已经有数填在那个位上的情况是要处理一下的，我们只需要取一波最值

an要尽可能大的话就从upn取值，判断一下upn.y是否只为1，要特殊搞一下

最后反过来做一遍就得到序列了

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int N=2e5+1;
int n;
int a[N],cnt[N];
struct Eyz {
    int x,y;
    bool operator < (const Eyz &a) const {return x<a.x||x==a.x&&y<a.y;}
}up[N],dn[N];

int main() {
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (a[1]>1) {printf("-1");return 0;}
    up[1].x=up[1].y=dn[1].x=dn[1].y=1;
    for (int i=2;i<=n;i++) {
        if (up[i-1].y+1>2) {
            up[i].x=up[i-1].x+1;up[i].y=1;
        }
        else up[i].x=up[i-1].x,up[i].y=up[i-1].y+1;
        if (dn[i-1].y+1>5) {
            dn[i].x=dn[i-1].x+1;dn[i].y=1;
        }
        else dn[i].x=dn[i-1].x,dn[i].y=dn[i-1].y+1;
        if (a[i]) {
            Eyz u,d;
            u.x=a[i];u.y=2;
            d.x=a[i];d.y=1;
            up[i]=min(up[i],u);
            dn[i]=max(dn[i],d);
            if (up[i].x<a[i]||dn[i].x>a[i]) {printf("-1");return 0;}
        }
    }
    Eyz ans=up[n];
    if (ans.y==1) {ans.x--;ans.y=5;}
    if (ans<dn[n]) {printf("-1");return 0;}
    a[n]=ans.x;cnt[ans.x]++;
    for (int i=n-1;i>=1;i--) {
        a[i]=min(a[i+1],up[i].x);
        if (cnt[a[i]]==5) a[i]--;
        cnt[a[i]]++;
    }
    printf("%d\n",ans.x);
    for (int i=1;i<=n;i++) printf("%d ",a[i]);
    fclose(stdin);fclose(stdout);
}