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 计蒜客的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。