[NC记录]AT2266 [AGC008D] K-th K
command_block
2021-03-01 09:11:43
**题意** ： 给你一个长度为 $n$ 的序列 $X$ ，构造否满足下列条件的序列 $A$ ，或指出无解。
- $a$ 的长度为 $n^2$ ，并数字 $1\sim n$ 都各出现恰好 $n$ 次。
- 数字 $i$ 在 $A$ 中第 $i$ 次出现的位置是 $X_i$。
$n\leq 500$ ，时限$\texttt{2s}$。
------------
在被 $X$ 钦定的若干位置上，需要放置的数已经确定，且前后所需放置的个数也已经确定。
于是，哪个数的 $\rm deadline$ 更近就先放哪个数即可。
暴力实现，复杂度即为 $O(n^3)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 505
using namespace std;
int n,x[MaxN],o[MaxN],ans[MaxN*MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&x[i]);
ans[x[i]]=i;
o[i]=i-1;
}x[0]=n*n+2;
for (int i=1;i<=n*n;i++){
if (ans[i]){
int p=ans[i];
if (o[p])
{puts("No");return 0;}
o[p]=n-p;
x[p]=n*n+1;
}else {
int p=0;
for (int k=1;k<=n;k++)
if (o[k]&&x[k]<x[p])p=k;
if (!p)
{puts("No");return 0;}
o[ans[i]=p]--;
}
}puts("Yes");
for (int i=1;i<=n*n;i++)
printf("%d ",ans[i]);
return 0;
}
```