【AtCoder Grand Contest 008 D】K-th K | Mrsrz's blog

贪心。

题目大意：

给定长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$，要求构造一个长度为 $n^2$ 的数列满足：

1. $1\sim n$ 每个数恰好出现 $n$ 次。
2. 数 $i$ 第 $i$ 次出现的位置为 $a_i$。

输出方案或说明无解。

题解：

对 $i$ 按照 $a_i$ 从小到大排序。我们从前往后考虑。考虑到一个位置时，我们把 $i-1$ 个数插在最前面的空格处，即满足第 $i$ 次出现在 $a_i$。并且我们使用最前面的位置，保证后面都尽可能优。

然后我们再从后往前按照这个方法进行即可。

如果不能插入，则说明无解。

Code：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=6666666;
int n;
pair<int,int>X[N];
queue<int>q;
bool vis[N];
int ans[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    scanf("%d",&X[i].first),X[i].second=i;
    sort(X+1,X+n+1);
    for(int i=1;i<=n;++i){
        for(int j=X[i-1].first+1;j<X[i].first;++j)q.push(j);
        ans[X[i].first]=X[i].second;
        vis[X[i].first]=1;
        for(int j=1;j<X[i].second;++j){
            if(q.empty()){puts("No");return 0;}
            int u=q.front();q.pop();
            vis[u]=1,ans[u]=X[i].second;
        }
    }
    while(!q.empty())q.pop();
    X[n+1].first=n*n+1;
    for(int i=n;i;--i){
        for(int j=X[i+1].first-1;j>X[i].first;--j)if(!vis[j])q.push(j);
        for(int j=1;j<=n-X[i].second;++j){
            if(q.empty()){puts("No");return 0;}
            int u=q.front();q.pop();
            vis[u]=1,ans[u]=X[i].second;
        }
    }
    puts("Yes");
    for(int i=1;i<=n*n;++i)
    printf("%d ",ans[i]);
    return 0;
}