一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A[i] >= H），炮弹会被挡住并落在i - 1处，则A[i - 1] + 1。如果H <= A[0]，则这个炮弹无效，如果H > 所有的A[i]，这个炮弹也无效。现在给定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}。
Input
第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)。Output
输出共M行，每行一个数，对应最终的地形高度。Input示例
9 11 1 2 0 4 3 2 1 5 7 2 8 0 7 6 5 3 4 5 6 5Output示例
2 2 2 4 3 3 5 6 7
首先看到这题与丢盘子一题很像，所以后面又用丢盘子的方法又做了一次，发现更慢，如题
1 首先考虑n平方肯定爆的，所以开一个数组zhiyin[]保存后面大于它的第一个点，如果大于这个点就直接根据数组保存的坐标访问
2 要注意的是高度变化，zhiyin数组就要更新或者处理（都可以）处理可以是while语句判断前推，
3 如果是最大zhiyin应保存为0，若大于该点高度，且判断为0，直接break，因为后面没有点比他高了，直接跳过
附上代码：
#include<iostream> #include <algorithm> #include <string.h> #include <string> #include <stack> #include<cstdio> #include <set> using namespace std; int main() { long long int numd,nump,di[50000],temp,temp1,zhiyin[50000],pao,low,high,i,j; scanf("%lld%lld",&numd,&nump); memset(zhiyin,0,sizeof(zhiyin)); for(i=0;i<numd;i++) scanf("%lld",&di[i]); for(i=1;i<numd;i++) //规定0 { if(di[i]>di[0]) { zhiyin[0]=i; break; } } temp=numd-1; for(i=1;i<temp;i++) //初使化zhiyin { if(di[i]>di[i-1]) //增长纠正 { low=zhiyin[i-1]; while(di[low]<=di[low-1]) low--; } else low=i+1; for(;low<numd;low++) if(di[low]>di[i]) { zhiyin[i]=low; break; } } while(nump--) //发炮 { scanf("%lld",&pao); for(i=0;i<numd;) { if(pao>di[i]) { if(zhiyin[i]==0) break; while(di[zhiyin[i]]<=di[zhiyin[i]-1]) //jiu zheng { zhiyin[i]--; } while(di[zhiyin[i]]>di[i]) zhiyin[i]--; zhiyin[i]++; i=zhiyin[i]-1; } else if(i!=0) //di yu { di[i-1]++; break; } else break; i++; } } for(i=0;i<numd;i++) printf("%lld\n",di[i]); return 0; }
然后我想试试盘子方法，结合二分会不会更快
1 :用ma数组保存从0到i 的最高值ma[i],ma[0]就是他本身高度
2 :二分搜索点mid ,在点mid+1的ma高度大于等于炮弹，且ma高度小于炮弹高度的点，也就是ma值的增高点
附上代码：
#include<iostream> #include<cstdio> using namespace std; int numd,nump,di[50000],temp,ma[50000],pao,low,high,i,mid; int main() { scanf("%d%d",&numd,&nump); scanf("%d",&di[0]); ma[0]=di[0]; for(i=1;i<numd;i++) { scanf("%d",&di[i]); if(di[i]>ma[i-1]) ma[i]=di[i]; else ma[i]=ma[i-1]; } while(nump--) //发炮 { scanf("%d",&pao); if(pao<=di[0]) continue; low=0; high=numd-1; temp=-1; while(low<=high) { mid=(low+high)/2; if(ma[mid]>=pao) { if(ma[mid-1]<pao) { temp=mid-1; break; } else high=mid-1;; } if(ma[mid]<pao) { if(ma[mid+1]>=pao) { temp=mid; break; } else low=mid+1; } } if(temp==-1) continue; di[temp]++; if(ma[temp]<di[temp]) { ma[temp]=di[temp]; } } for(i=0;i<numd;i++) printf("%d\n",di[i]); return 0; }
