当前位置: 代码迷 >> 综合 >> OJ 1470 小鱼的海岛之旅
  详细解决方案

OJ 1470 小鱼的海岛之旅

热度:36   发布时间:2024-02-01 11:47:12.0

描述

暑假到了,小鱼到海岛上玩。

从水平方向看海岛可以看成n个小块,每一个小块都有一个高度hi,

水位一开始为0,随着水位的上升,海岛分成了若干块。

现在有m个询问,求当水位为ai时,海岛会分成多少块。


输入
第一行输入两个正整数n,m,分别表示海岛小块个数和询问个数。

第二行输入n个整数hi,表示每一块的高度。

第三行输入m个整数ai,表示每一个询问。


输出
共m行,分别对应m个询问的答案。

输入样例 1

7 3
1 2 3 1 2 1 3
1 2 3
输出样例 1

3
2
0

 

对于这题我们可以使用数组来表示每块的高度,然后输入了水位之后让每一个高度减去水位即可,如果的减之后水位大于0而且它的前一项小于或等于0,那么这就是一块的开头,那么计数就要加每次遇到开头就加即可得到数据,但是题目说明是水位到了多少,所以原始数组要一直保持,我们可以使用一个临时数组去保存变更的数据。

#include <iostream>
#include <algorithm>using namespace std;int main()
{int n,m,x;while(cin>>n>>m){int a[n],b[n];for(int i=0; i<n; i++)cin>>a[i];while(m--){cin>>x;int sum=0;for(int i=0; i<n; i++){b[i]=a[i]-x;if(b[i-1]<=0&&b[i]>0)sum++;}cout<<sum<<endl;}}return 0;
}