题目：
我是超链接
题解：
首先很显然我们有一个贪心的思路：后序遍历从大到小填数，trick一下可以得到60pts 但是对于下面这组数据显然是没有用的 4 2 1 1 1 2 我们贪心的答案是1 1 1 2，但更优的方案是1 1 2 1 那么考虑一下怎么消除这种有重复数字的情况，我们发现只有排名一样的情况下需要考虑前后 我们可以按位贪心，即在给后面预留出足够位置的情况下先填好前面的 我们可以从小到大排序，类似拓扑的处理方法吧，查找区间第k大可以用线段树搞定，而且线段树在位置的优先选择上也很好，把小的尽量往后安
代码：
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=
500005;
int tot,nxt[N],point[N],v[N],size[N],sum[N*
4],a[N],ans[N];
void addline(
int x,
int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; size[x]+=size[y];}
void add(
int now,
int l,
int r,
int x,
int v)
{
sum[now]+=v;
if (l==r)
return;
int mid=(l+r)>>
1;
if (x<=mid) add(now<<
1,l,mid,x,v);
else add(now<<
1|
1,mid+
1,r,x,v);
}
int find(
int now,
int l,
int r,
int k)
{
if (l==r)
return l;
int mid=(l+r)>>
1;
if (sum[now<<
1|
1]<k)
return find(now<<
1,l,mid,k-sum[now<<
1|
1]);
else return find(now<<
1|
1,mid+
1,r,k);
}
int main()
{
int n;
double k;
scanf(
"%d%lf",&n,&k);
for (
int i=
1;i<=n;i++)
scanf(
"%d",&a[i]),size[i]=
1;
sort(a+
1,a+n+
1);
int last=
1;
for (
int i=n;i>=
1;i--) addline((
int)
floor(i/k),i);
for (
int i=point[
0];i;i=nxt[i]) add(
1,
1,n,v[i],size[v[i]]);
for (
int i=
1;i<=n;i=last)
{
while (last<=n && a[last]==a[i]) last++;
for (
int j=last-i;j>=
1;j--)
{
int t=find(
1,
1,n,j);
ans[t]=a[i];
add(
1,
1,n,t,-size[t]);
for (
int l=point[t];l;l=nxt[l]) add(
1,
1,n,v[l],size[v[l]]);
}
}
for (
int i=
1;i<=n;i++)
printf(
"%d ",ans[i]);
}
