解题报告:51nod 加农炮
2024-08-27 18:54:34
2017-10-07 16:15:16
writer;pprp
题目来源: Codility
基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
一个长度为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 可以暴力求解:直接去做
代码如下:
/*
@theme:51nod 加农炮
@writer:pprp
@begin:16:00
@end:16:17
@declare:暴力求解
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdiO> using namespace std;
int M, N;
int h[]; int main()
{
freopen("in.txt","r",stdin);
memset(h,,sizeof(h));
cin >> M >> N;
int maxh = -;
for(int i = ; i < M ; i++)
{
cin >> h[i];
if(maxh < h[i])
{
maxh = h[i];
}
}
int cmp;
for(int i = ; i < N ; i++)
{
cin >> cmp;
if(cmp <= h[] || cmp > maxh)
continue;
for(int j = ; j < M ; j++)
{
if(h[j] >= cmp)
{
h[j-]++;
break;
}
}
}
for(int i = ; i < M ; i++)
{
cout << h[i] << endl;
} return ;
}
预处理,用lower_bound做
/*
@theme:51nod 加农炮
@writer:pprp
@begin:16:20
@end:
@declare:预处理
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdiO> using namespace std;
int h[+];
int canno[+];
int M, N; int main()
{
freopen("in.txt","r",stdin); cin >> M >> N; int maxh = -; for(int i = ; i < M ; i++)
{
cin >> h[i];
maxh = max(maxh,h[i]);
canno[i] = maxh;// 预处理
}
int cmp;
for(int i = ; i < N ; i++)
{
cin >> cmp;
int j;
if(cmp <= h[] || cmp > maxh)
continue;
j = lower_bound(canno,canno+M,cmp)-canno;
h[j-]++;
canno[j-] = max(canno[j-],h[j-]);
}
for(int i = ; i < M ; i++)
cout << h[i] << endl; return ;
}
最新文章
- 串口实现FIFO接受数据
- ICollection
- jQuery学习笔记--JqGrid相关操作 方法列表(上)
- ionic单页面应用中微信分享的问题总结
- Linux下如何删除Oracle
- 27款后台管理页面设计 DIV+CSS+JS
- iOS开发拓展篇—xib中关于拖拽手势的潜在错误
- SpringMVC后缀
- MySQL中字符串函数详细介绍
- process thread Fiber(linux)
- POJ1699Best Sequence(DFS)
- JQUERY1.9学习笔记 之层级选择器(四)
- php 程序员的历程
- LINQ to Entities does not recognize the method &#39;System.DateTime ToDateTime(System.String)&#39; method
- ASP.NET Core MVC/WebAPi如何构建路由?
- winform / Dev全局皮肤组件
- 浅谈JS的继承
- margin:0px auto和text-align:center区别
- css为第几个倍数元素添加样式
- 我写的.net相关的文章