51nod 1287加农炮
2024-09-01 19:39:54
一个长度为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
5
Output示例
2
2
2
4
3
3
5
6
7 思路:线段树+二分,利用线段树存储每一个区间内的山峰最高值,通过二分查找找出高度大于等于当前炮弹的山峰下标k,将k-1位置的山峰高度+1即可
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio> using namespace std;
//typedef long long LL;
const int maxn = ;
int a[maxn],rs[maxn<<];
int n,m;
void pushup(int rt){
rs[rt] = max(rs[rt<<],rs[rt<<|]);
}
void build(int l,int r,int rt)
{
if(l==r){
rs[rt] = a[l];
return;
}
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
void update(int x,int l,int r,int rt)
{
if(l==r){
rs[rt]++;
return;
}
int mid=(l+r)>>;
if(x<=mid) update(x,l,mid,rt<<);
else update(x,mid+,r,rt<<|);
pushup(rt);
}
int query(int x,int l,int r,int rt)//根据x的值找出从左往右找出第一个能碰到的山峰的下标
{
if(l==r) return l;
int mid = (l+r)>>;
if(x<=rs[rt<<]) query(x,l,mid,rt<<);
else query(x,mid+,r,rt<<|);
}
int Query(int x,int l,int r,int rt)//根据点查询数据
{
if(l==r)return rs[rt];
int mid = (l+r)>>;
if(x<=mid)Query(x,l,mid,rt<<);
else Query(x,mid+,r,rt<<|);
}
int main()
{
ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
while(cin>>n>>m){
int x;
memset(rs,,sizeof(rs));
for(int i=;i<=n;i++)
cin>>a[i];
build(,n,);
for(int i=;i<=m;i++){
cin>>x;
// if(x>rs[1]||x<=a[1])continue;一开始在这里卡了好久 后头想起来第一个位置的高度可能也会更新所以每一次都需要查询
if(x>rs[]||x<=Query(,,n,))continue;
int k=query(x,,n,);
update(k-,,n,);//更新前一个点的高度
}
for(int i=;i<=n;i++)
cout<<Query(i,,n,)<<endl;
}
return ;
}
最新文章
- 拖动对象ondrag
- 【Java EE 学习 43】【SVN版本控制工具】【CVS版本控制工具】
- [Leetcode][JAVA] Minimum Window Substring
- sql 几点记录
- 排队打饭 sdut 2443【最简单的贪心法应用举例】
- c# 高效率导出多维表头excel
- crontab 安装 和一些 简单的命令
- Redis几个认识误区(转)
- Python中的高级数据结构
- js 将网页内容生成图片
- hadoop学习;安装jdk,workstation虚拟机v2v迁移;虚拟机之间和跨物理机之间ping网络通信;virtualbox的centos中关闭防火墙和检查服务启动
- windows环境自动获取SVN仓库当前版本
- 解决getJSON的缓存问题
- 学习MySQL(下)
- PHP学习笔记 01 之表单传值
- Ubuntu18.10下配置PHP7.2 + Apache2 + Mysql5.7
- 006-CSS引入外部字体
- Java Cookie工具类
- springmvc拦截器的简单了解
- VS“新建网站”与“新建Asp.Net Web 应用程序”的区别
热门文章
- SPSS能做Cochran-Armitage趋势检验吗
- Directx11教程(66) D3D11屏幕文本输出(1)
- 【转载】CPU相关总结
- Seata 0.7.0 正式发布
- <;>; 是不等号的意思
- 2019.9.19登陆注册猜数字给奖品combo
- Introduction to 3D Game Programming with DirectX 12 学习笔记之 --- 第十四章:曲面细分阶段
- ArcMap影像纠偏
- Java练习 SDUT-1184_拍皮球
- 云原生生态周报 Vol. 8 | Gartner 发布云原生趋势