仓鼠的鸡蛋

NC226170. 仓鼠的鸡蛋

描述

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

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

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

输入描述

首先输入一个，代表测试数据数. 每个案例的第一行输入三个整数，，，. 第二行输入个整数，。

输入保证

输出描述

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

示例1

输入:

1
7 5 2
5 5 1 4 3 3 1

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 172ms, 内存消耗: 22520K, 提交时间: 2021-09-10 19:34:04

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ls u<<1
#define rs u<<1|1
const int N=3e5+10;
const int M=4*N;
int w[M],num[M],n,m,k;
int up(int l,int r,int u,int k)
{
    int ans=-1;
    if(l==r)
    {
        num[u]--;w[u]-=k;
        if(num[u]==0)w[u]=0;
        return l;
    }
    int mid=(l+r)>>1;
    if(w[ls]>=k)
    {
        ans=up(l,mid,ls,k);
    }
    else if(w[rs]>=k)
    {
        ans=up(mid+1,r,rs,k);
    }
    w[u]=max(w[ls],w[rs]);
    return ans;
}
signed main()
{
    int T;cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        for(int i=1;i<=4*n;++i){w[i]=m;num[i]=k;}
        for(int i=1;i<=n;++i)
        {
            int x;scanf("%lld",&x);
            printf("%lld\n",up(1,n,1,x));;
        }
    }
}