CF1517C

题目链接

思路

如果左边有位置就往左边填充，否则往下填充，不难说明正确性。填充方式可以使用dfs。

时间复杂度：\(O(n^2)\)

代码：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int p[505],a[505][505],cnt[505];
void dfs(int i,int j,int col){
    //cout<<i<<" "<<j<<" "<<col<<endl;
    if(!a[i][j]){
        cnt[col]++;a[i][j]=col;
    }
    if(!a[i][j-1]&&j>1&&cnt[col]<col)dfs(i,j-1,col);
    else if(cnt[col]<col)dfs(i+1,j,col);
}
int main(){
    int n=read();
    rep(i,1,n){
        a[i][i]=p[i]=read();
        cnt[p[i]]=1;
    }
    rep(i,1,p[1])a[i][1]=p[1];
    rep(i,2,n){
        dfs(i,i,p[i]);
    }
    rep(i,1,n){
        rep(j,1,i)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}