 /**//*
给出n,k,b[],n<=1000
b[i]表示最后要求的一个n的排列中a[],a[t] =i的这个数左边满足a[j]>=i+k的个数
求字典序最小的一个满足上面条件排列a[]
不会贪心,看了别人的
用类似拓扑排序那样子,每次寻找最小的而且b[i] = 0的输出, ------------------ Orz
然后更新b[j], b[j]--
其中 i>=j+k 因为i已经放在前面了,自然后面的需要a[j]>=i+k的个数就少1了
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;


int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif
 for (int n, k; ~scanf("%d%d", &n, &k); ) {
vector<int> b(n+1);
 for (int i = 1 ; i <= n ; i++) {
scanf("%d", &b[i]);
}
 for (int i = 1, j; i <= n; i ++) {
 for(j = 1; j <= n ; j++) {
 if(b[j] == 0) {
break;
}
}
 if(i > 1) {
putchar(' ');
}
cout<<j;
b[j] = -1;
 for (int p = 1; p + k <= j; p++) {
b[p] --;
}
}
cout<<endl;
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|