题意
给你一个数组,有n个数,有m个操作,每次读入一个x,对数组a中小于等于x的数进行加x操作,问m次操作后输出数组元素。
思路
我们算一下最多每个数会进行多少次加操作。
假如一个元素为1。
第一个我们让它加1,变成2。
第二次我们让它加2,变成4。
第三次我们让它加4,变成8。
第四次我们让它加8,变成16。
我们发现每个元素都是倍增的,也就是说每个元素最多也只会进行次加操作,所以我们可以直接用一个优先队列,每次取出小于等于x的元素进行加操作,然后再塞回队列,这样就可以解决问题,这样的时间复杂度是()是可以过的,但是要注意的是当x是0的时候我们要进行跳过,否则如果初始元素都是0的时候,会每次都取出所有元素,这样的时间会爆的。
小优化
我们可以用线段树来维护区间和,区间最大值,区间最小值,然后每次对1到n中的数进行加x操作,如果当前区间最大值小于等于x的时候,我们可以直接对这个区间进行加x操作,如果当前区间的最小值都大于x的时候就可以直接退出,这样就不用一个一个取元素再添元素,这样可以使效率更快。
代码
#include <bits/stdc++.h> #define ll long long //#define fi first //#define se second #define pb push_back #define me memset const int N = 1e6+10; const int MOD = 99824353; const int INF = 0x3f3f3f3f; using namespace std; typedef pair<int,int> PII; //typedef pair<ll,ll> PLL; struct PLL { ll fi,se; }p[N]; bool operator<(PLL a,PLL b) { return a.fi>b.fi; } ll a[N]; int main() { int n,m; cin>>n>>m; for(int i=1 ; i<=n ; i++) cin>>p[i].fi,p[i].se=i; priority_queue<PLL>q; for(int i=1 ; i<=n ; i++) q.push(p[i]); while(m--) { int x; cin>>x; if(x==0) continue; vector<PLL>v; //cout<<q.size()<<" "<<q.top().fi<<endl; while(!q.empty()&&x>=q.top().fi) { //cout<<q.top().fi<<endl; v.push_back({q.top().fi+x,q.top().se}); q.pop(); } for(auto x:v) q.push(x); } while(!q.empty()) { PLL pp=q.top(); q.pop(); a[pp.se]=pp.fi; } for(int i=1 ; i<=n ; i++) cout<<a[i]<<" "; cout<<endl; return 0; }
总结
这一题的关键就是要想到每个数最多只会被加次。