牛客仓鼠的鸡蛋

本文主要是介绍牛客仓鼠的鸡蛋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分析一下判断语句

如果能放就输出位置

不能放就输出-1

不能放的条件是最大值小于要放的鸡蛋数量，线段树维护最大值

放的位置用线段树二分

每个篮子不能放超过k堆鸡蛋，记录一下每个篮子放的次数，次数等于k后给最大值附上0即可

// Problem: 仓鼠的鸡蛋
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19684/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=3e5+9;
int a[N],c[N<<2];
int n,m,k;
struct node{ll mx;
}seg[N<<2];
ll tl(ll x){return x<<1;
} 
ll tr(ll x){return x<<1|1;
}
void pushup(int id){seg[id].mx=max(seg[tl(id)].mx,seg[tr(id)].mx);
}
void build(int id,int l,int r){if(l==r){seg[id].mx=a[l];return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);
}
bool inrange(int L,int R,int l,int r){return L>=l && R<=r;
}
bool outofrange(int L,int R,int l,int r){return L>r || l>R;
}
ll ask(int id,int l,int r,ll v){if(l==r){return l;}int mid=(l+r)>>1;if(seg[tl(id)].mx>=v){return ask(tl(id),l,mid,v);}else{return ask(tr(id),mid+1,r,v);}
}
void update(int id,int l,int r,int pos,ll v){if(l==r){seg[id].mx+=v;c[id]++;if(c[id]==k){seg[id].mx=0;}return;}int mid=(l+r)>>1;if(mid>=pos){update(tl(id),l,mid,pos,v);}else{update(tr(id),mid+1,r,pos,v);}pushup(id);
}
void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++){a[i]=m;	}build(1,1,n);for(int i=1;i<=n;i++){int x;cin>>x;if(x>seg[1].mx){cout<<-1<<'\n';continue;}ll pos=ask(1,1,n,x);update(1,1,n,pos,-x);cout<<pos<<'\n';}for(int i=1;i<=n*4;i++){c[i]=0;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

这篇关于牛客仓鼠的鸡蛋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---