题意简述:给你一个长度为(N)的整数序列(x),请判断是否存在一个满足下列条件的整数序列(a),如果存在,请构造一种方案。
1.(a)的长度为(N^2)并且满足数字(1,2,3,cdots,N)都各出现恰好(N)次
2.对于(1<=i<=N),数字(i)在(a)中第(i)次出现的位置是(x_i)
我他么写这种傻逼题写了1.5h,cao
非常简单,我们可以考虑贪心,将二元组((x,i))按(x)排序,然后(x_i)放(i),前面暴力放最前面空的(i-1)个,再倒着做一遍就可以了
时间复杂度(O(N^3))
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=510;
struct fk{int x,id;}q[N];
int n,a[N*N],cnt[N],flag;
bool cmp(fk a,fk b){return a.x<b.x;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&q[i].x),q[i].id=i;
sort(q+1,q+n+1,cmp);
for(int i=1;i<=n;i++){
int id=q[i].id;
a[q[i].x]=id;++cnt[id];
for(int j=1;j<q[i].x;j++){
if(cnt[id]==id)break;
if(!a[j])a[j]=id,++cnt[id];
}
if(cnt[id]<id)flag=1;
}
if(flag){puts("No");return 0;}
flag=0;
for(int i=n;i>=1;i--){
int id=q[i].id;
for(int j=n*n;j>q[i].x;j--){
if(cnt[id]==n)break;
if(!a[j])a[j]=id,++cnt[id];
}
if(cnt[id]<n)flag=1;
}
if(flag){puts("No");return 0;}
puts("Yes");
for(int i=1;i<=n*n;i++)printf("%d ",a[i]);
puts("");
}