首页 > 代码库 > 岛屿（洛谷 U5399）
岛屿（洛谷 U5399）
题目背景
放假了，Lkw和mm到岛上旅游。阳光明媚，风景秀丽。正当Lkw和mm享受眼前这旖旎的风光时，突降大雨，小岛上开始积水，没过几分钟，水便快要触及膝盖。Lkw和mm意识到了事态的严重性，赶紧向高地跑去，可在涌动的人流中，Lkw和mm失散了...水越涨越高，Lkw拿着望远镜四处寻找，耳边不停地传来mm的呼喊，可就是不见mm的身影……焦急的Lkw想知道mm可能在几个区域，你能帮助他么？
题目描述
从水平方向看，我们把岛屿分成n个小块，每个部分用一个数h表示高度，每个区域由相连的小块组成。一开始，水位为0，整个岛屿只有一个区域，在水上涨的过程中，某些小块会被淹没，这样原本相连的区域就会变成多个，假设每个时刻水位会上涨1，现在Lkw想知道q个时刻的情况。
输入输出格式
输入格式：
输入第一行包含一个整数n
第二行包含n个整数，分别表示每个小块的高度
第三行包含一个整数q
第四行包含q个整数，表示要询问的q个时刻。
输出格式：
输出共包含q行，每行表示该时刻mm可能在的区域有几个。
输入输出样例
输入样例#1：
7 1 2 3 1 2 1 3 3 1 2 3
输出样例#1：
3 2 0
说明
对于30%的数据n<=1000 q<=1000
对于100%的数据n<=100000 q<=100000 h<=109
输入保证q单调递增
/* 将数列按照高度排序，先计算出一个开始时的区域数ans，当要下落的石块左右两边都已经下落时，ans--；当要下落的石块的左右两边都没下落时，ans++。 第一遍做只考虑了下落的那个时刻，没考虑其他时刻，WA了。 */ #include<iostream> #include<algorithm> #define N 100010 using namespace std; int n,tmp,now=1,ans=1; struct node { int h; int x; bool operator < (node t)const { return t.h>h; } };node a[N]; bool flag[N]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>tmp; a[i].h=tmp; a[i].x=i; flag[i]=1; } sort(a+1,a+n+1); cin>>n; for(int i=1;i<=n;i++) { cin>>tmp; while(a[now].h<=tmp&&now<=n) { int t=-1,x=a[now].x; if(x>1&&flag[x-1]) t++; if(x<n&&flag[x+1]) t++; ans+=t; flag[x]=0; now++; } cout<<ans<<endl; } return 0; }
岛屿（洛谷 U5399）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。