題面

一個長度為M的正整數數組A，表示從左向右的地形高度。測試一種加農炮，炮彈平行于地面從左向右飛行，高度為H，如果某處地形的高度大于等于炮彈飛行的高度H（Ai >= H），炮彈會被擋住并落在i - 1處，則Ai?1 + 1。如果H <= A0，則這個炮彈無效，如果H > 所有的Ai，這個炮彈也無效。現在給定N個整數的數組B代表炮彈高度，計算出最后地形的樣子。
例如：地形高度A = {1, 2, 0, 4, 3, 2, 1, 5, 7}, 炮彈高度B = {2, 8, 0, 7, 6, 5, 3, 4, 5, 6, 5}，最終得到的地形高度為：{2, 2, 2, 4, 3, 3, 5, 6, 7}。
1 <= m, n <= 50000 0 <= Ai <= 1000000 0 <= Bi <= 1000000

分析

依次加入每個炮彈，線段樹維護最大值，每次找出第一個高度大于等于當前炮彈飛行高度的位置，修改此位置前一個位置的高度。
感覺是個模擬..

代碼

#include<bits/stdc++.h> using namespace std; #define N 50050 #define lc (p<<1) #define rc (p<<1|1) #define mid (t[p].l+t[p].r>>1) int n,m,x,k; int a[N]; struct email {int l,r,maxx; }t[N*4];inline void pushup(int p) {t[p].maxx=max(t[lc].maxx,t[rc].maxx); }inline void build(int p,int l,int r) {t[p].l=l;t[p].r=r;if(l==r){t[p].maxx=a[l];return ;}int bm=l+r>>1;build(lc,l,bm);build(rc,bm+1,r);pushup(p); }inline void update(int p,int x) {if(t[p].l==t[p].r){t[p].maxx=a[x];return ;}if(x<=mid)update(lc,x);if(x>mid)update(rc,x);pushup(p); }inline int query(int p,int x) {if(t[p].l==t[p].r)return t[p].l;if(x<=t[lc].maxx)return query(lc,x);if(x>t[lc].maxx)return query(rc,x); }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);for(int i=1;i<=m;i++){scanf("%d",&x);if(x<=a[1]||x>t[1].maxx)continue;k=query(1,x);a[k-1]++;update(1,k-1);}for(int i=1;i<=n;i++)printf("%d\n",a[i]);return 0; }

?

轉載于:https://www.cnblogs.com/NSD-email0820/p/9806373.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【51NOD1287】加农炮的全部內容，希望文章能夠幫你解決所遇到的問題。

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