本文共 1201 字,大约阅读时间需要 4 分钟。
第1行:2个数M, N中间用空格分隔,分别为数组A和B的长度(1 <= m, n <= 50000)第2至M + 1行:每行1个数,表示对应的地形高度(0 <= A[i] <= 1000000)。第M + 2至N + M + 1行,每行1个数,表示炮弹的高度(0 <= B[i] <= 1000000)。
输出共M行,每行一个数,对应最终的地形高度。
9 1112043215728076534565
222433567
另建一个数组conno,表示h[]的递增序列,用二分找炮弹打过来的高地,将其之前的土地高度+1,然后更新高地高度。详见代码
const int maxn=5e4+10;int n,m;int h[maxn],conno[maxn];int main(){ ios::sync_with_stdio(false); cin>>n>>m; int maxh=-1; memset(conno,0,sizeof(conno)); for(int i=1;i<=n;i++) { cin>>h[i]; maxh=max(maxh,h[i]); conno[i]=maxh; } int gun,pos; for(int i=1;i<=m;i++) { cin>>gun; if(gun<=conno[0] || gun>conno[n]) continue; pos=lower_bound(conno+1,conno+1+n,gun)-conno; h[pos-1]++; conno[pos-1]=max(conno[pos-1],h[pos-1]); } for(int i=1;i<=n;i++)cout<<
转载地址:http://peali.baihongyu.com/