Description

 

Input

第一行一个数 n，表示序列的长度。

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

Output

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

 

Sample Input

【样例 1 输入】70 1 0 0 0 3 0【样例 2 输入】40 0 0 3

Sample Output

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

 

Data Constraint

对于 30% 的数据，n ≤ 1000；

对于另外 30% 的数据，数据保证随机生成；

对于 100% 的数据，2 ≤ n ≤ 2 × 10^5 , 0 ≤ ai ≤ 10^5。

 

 

题解

• 我们可以先定义一个up数组和一个down数组，up表示可能走到的最大值，down表示可能走到的最小值
• 那么对于没有填的数，先不考虑填了的数，up两个进1，down五个进1肯定是它们要表示的值
• 那么如果对于填了的数，先考虑上界
• 那么现将上界定到填的数，然后长度为2，如果填的数等于上界，在上界求出来的长度和2取min
• 下界的话，将下界定到填的数，长度为1
• 如果最后up[n].l=1的话，也就说明了up[n].x不可以填的，不是最大值
• 因为在所有情况都是最优下，只剩1的长度，没有比这种情况更优的，所以up[n].x是填不了的
• 现在最大值也确定了，只要找到一种方法填数就好了
• 然后，从后往前跑，那么对于有填的数，直接s[a[i]]++
• 没填的数，在a[i+1]和up[i].x取min值
• 如果s[min]=5的话，往前走一位就好了
• 还有-1的情况，有以下几种情况：
• ①a[i]>1
• ②up[n].x<down[n].x
• ③up[i].x<a[i]||down[i].x>a[i]

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 struct edge {
   int x,l;}up[200010],down[200010]; 7 int a[200010],n,s[200010],k; 8 int main() 9 {10     scanf("%d",&n);11     for (int i=1;i<=n;i++) scanf("%d",&a[i]);12     if (a[1]>1) 13     {14         printf("-1");15         return 0;16     }17     up[1].x=1,up[1].l=1;18     down[1].x=1,down[1].l=1;19     for (int i=2;i<=n;i++)20     {21         down[i]=down[i-1];22         if (++down[i].l>5) ++down[i].x,down[i].l=1;23         up[i]=up[i-1];24         if (++up[i].l>2) ++up[i].x,up[i].l=1;25         if (a[i]>0)26         {27             if (up[i].x>a[i]) up[i].x=a[i],up[i].l=2; else if (up[i].x==a[i]) up[i].l=min(up[i].l,2);28             if (down[i].x
         
          a[i]) 30             {31                 printf("-1");32                 return 0;33             }34         }35     }36     if (up[n].l==1) up[n].x--,up[n].l=5;37     if (up[n].x
          
           =1;i--)45 {46 if(!a[i])47 {48 k=min(a[i+1],up[i].x);49 k-=s[k]==5,a[i]=k;50 }51 s[a[i]]++;52 }53 for (int i=1;i<=n;i++) printf("%d ",a[i]);54 return 0;55 }