Lpl and Energy-saving Lamps 计蒜客

本文主要是介绍Lpl and Energy-saving Lamps 计蒜客，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://nanti.jisuanke.com/t/30996

暴力跑一遍每个月 再暴力跑一遍房间序列 看以当前灯泡数量能换哪个房间 维护区间最小值 线段树二分查找

最多1e5个房间 都换完了就直接退出

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=0x3f3f3f3f3f3f3f3f;struct node
{int l;int r;ll val;
};vector <int> pre[100010];
node tree[400010];
ll ans2[100010];
ll m,gou;
int ans1[100010];
int n,q,pos;void pushup(int cur)
{tree[cur].val=min(tree[2*cur].val,tree[2*cur+1].val);
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].val=N;if(l==r){scanf("%lld",&tree[cur].val);return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void query(ll val,int cur)
{if(tree[cur].l==tree[cur].r){gou=tree[cur].val;pos=tree[cur].l;return;}if(val>=tree[2*cur].val) query(val,2*cur);else query(val,2*cur+1);
}void update(int tar,int cur)
{if(tree[cur].l==tree[cur].r){tree[cur].val=N;return;}if(tar<=tree[2*cur].r) update(tar,2*cur);else update(tar,2*cur+1);pushup(cur);
}int main()
{ll sum;int i,j,p,num;scanf("%d%lld",&n,&m);build(1,n,1);scanf("%d",&q);for(i=1;i<=q;i++){scanf("%d",&p);pre[p].push_back(i);}sum=0,num=0;for(i=1;i<=100000;i++){if(num<n){sum+=m;while(tree[1].val<=sum&&num<n){query(sum,1);update(pos,1);sum-=gou;num++;}}for(j=0;j<pre[i].size();j++){ans1[pre[i][j]]=num,ans2[pre[i][j]]=sum;}}for(i=1;i<=q;i++){printf("%d %lld\n",ans1[i],ans2[i]);}return 0;
}

 

这篇关于Lpl and Energy-saving Lamps 计蒜客的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---