仓鼠与鸡蛋分配问题

仓鼠家里有n堆鸡蛋，每堆有ai​个鸡蛋，仓鼠准备了n个篮子(按照1,2,3,...n编号)，每个篮子最多能放m个鸡蛋，仓鼠想要把鸡蛋全部放在篮子里。

这时候，它想起了智乃酱说过，不能把鸡蛋都放在一个篮子里。所以它决定每个篮子不能放超过k堆鸡蛋。

因为仓鼠很懒，所以它每次都会按顺序拿起一堆鸡蛋，然后放在编号最小的，可行的篮子里。
现在它想知道，如果按照这样操作，每一堆鸡蛋会被放在哪个篮子里？

输入描述:

首先输入一个T(1≤T≤100)，代表测试数据数. 每个案例的第一行输入三个整数，n(1≤n≤3×10^5)，m(1≤m≤10^9)，k(1≤k≤10^6). 第二行输入n个整数，a1,a2,a3...(1≤ai≤109)。

输入保证sigma(n)<=1e6

输出描述:

输出n行，每行一个整数，第i行输出代表第i堆鸡蛋被放在哪个篮子里。(如果鸡蛋没被放在任何一个篮子里，输出"−1"

示例1

输入

1 7 5 2 5 5 1 4 3 3 1

输出

1 2 3 3 4 5 4

#include<bits/stdc++.h>

using namespace std;

const int MAXN=300005;

#define int long long

struct tnode

{

int maxx;

int l,r;

};

int n,m,k,cnt[MAXN];

struct Segment_Tree

{

tnode t[4*MAXN];

void update (int root)

{

int ch=root<<1;

t[root].maxx=max(t[ch].maxx,t[ch+1].maxx);

}

void buildt(int root,int l,int r)

{

t[root].l=l;

t[root].r=r;

if(l!=r)

{

int mid=(l+r)>>1;

int ch=root<<1;

buildt(ch,l,mid);

buildt(ch+1,mid+1,r);

update(root);

}

else

{

t[root].maxx=m;

cnt[l]=0;

}

}

int gao(int val)

{

int root=1;

while(t[root].l!=t[root].r)

{

if(t[root<<1].maxx>=val)

{

root<<=1;

}

else

{

root=root*2+1;

}

}

t[root].maxx-=val;

++cnt[t[root].l];

int ans=t[root].l;

if(cnt[t[root].l]==k)

{

t[root].maxx=0;

}

root>>=1;

while(root)

{

update(root);

root>>=1;

}

return ans;

}

};

Segment_Tree ST;

int x,T;

signed main()

{

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

cin>>T;

while(T--)

{

cin>>n>>m>>k;

ST.buildt(1,1,n);

for(int i=1; i<=n; ++i)

{

cin>>x;

if(x>m)

{

cout<<-1<<"n";

}

else

{

cout<<ST.gao(x)<<"n";

}

}

}

return 0;

}