[NC记录]AT2266 [AGC008D] K-th K
command_block
·
·
个人记录
题意 ： 给你一个长度为 n 的序列 X ，构造否满足下列条件的序列 A ，或指出无解。
------------
在被 $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;
}
```