51nod 1276 岛屿的数量神奇做法

xiaoxiao2021-02-28  4

有N个岛连在一起形成了一个大的岛屿,如果海平面上升超过某些岛的高度时,则这个岛会被淹没。原本的大岛屿则会分为多个小岛屿,如果海平面一直上升,则所有岛都会被淹没在水下。 给出N个岛的高度。然后有Q个查询,每个查询给出一个海平面的高度H,问当海平面高度达到H时,海上共有多少个岛屿。例如: 岛屿的高度为:{2, 1, 3, 2, 3}, 查询为:{0, 1, 3, 2}。 当海面高度为0时,所有的岛形成了1个岛屿。 当海面高度为1时,岛1会被淹没,总共有2个岛屿{2} {3, 2, 3}。 当海面高度为3时,所有岛都会被淹没,总共0个岛屿。 当海面高度为2时,岛0, 1, 3会被淹没,总共有2个岛屿{3} {3}。 Input 第1行:2个数N, Q中间用空格分隔,其中N为岛的数量,Q为查询的数量(1 <= N, Q <= 50000)。 第2 - N + 1行,每行1个数,对应N个岛屿的高度(1 <= A[i] <= 10^9)。 第N + 2 - N + Q + 1行,每行一个数,对应查询的海平面高度(1 <= Q[i] <= 10^9)。 Output 输出共Q行,对应每个查询的岛屿数量。 Input示例 5 4 2 1 3 2 3 0 1 3 2 Output示例 1 2 0

2

把岛屿和海平面都从小到大排序,这样有两个好处。

对于某一个海平面,我们碰到当前岛屿超过了,那么就不需要往后找了。

对于某一个岛屿,如果之前海平面超过了,那么标记一下,现在海平面可以不用管当前这个岛了。

建立一个sum=1,代表当前大岛的个数。

之后对于某一个海平面,从某个岛开始枚举。

如果当前岛在最左边,我们看看第二个岛是否被淹了,如果被淹了,那么sum-1.没被淹,那就不做处理。

如果当前岛在最右边,我们看看倒数第二个岛是否被淹了,如果被淹了,那么sum-1,否则不做处理

如果当前岛在中间地区,我们看看这个岛两边的两个岛是否被淹,如果都被淹了,那么sum--,如果都没被淹,那么sum++

之后标记一下这个岛被淹了。继续看下一个岛的情况。

直到某个岛不会被淹位置,记录当前海平面sum的值。

之后对于下一个海平面,继续从上一个枚举的位置出发,不要重置。因为对于下一个海平面一定能达到上一个海平面的“成就”

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; struct node {     long long height;     long long id; }daoyu[51000],haipingmian[51000]; bool cmp(node t1,node t2) {     if(t1.height==t2.height)         return t1.id<t2.id;     return t1.height<t2.height; } long long ans[51000]; long long vis[51000]; long long n,m; int main() {     cin>>n>>m;     for(long long i=1;i<=n;i++)     {         cin>>daoyu[i].height;         daoyu[i].id=i;     }     for(long long i=1;i<=m;i++)     {         cin>>haipingmian[i].height;         haipingmian[i].id=i;     }     sort(daoyu+1,daoyu+1+n,cmp);     sort(haipingmian+1,haipingmian+1+m,cmp);     memset(ans,0,sizeof(ans));     memset(vis,0,sizeof(vis));     long long sum=1;     long long dao=1;     for(long long i=1;i<=m;i++)//每一个海平面     {         while(daoyu[dao].height<=haipingmian[i].height&&dao<=n)         {             if(daoyu[dao].id==1)//如果当前岛是第一个             {                 if(vis[2]==1) //第二个岛已经淹了                 {                     sum--;//那么这个岛也淹了之后,总数-1                 }             }             else if(daoyu[dao].id==n)//如果当前岛是最后一个的话             {                 if(vis[n-1])                 {                     sum--;                 }             }             else             {                 if(vis[daoyu[dao].id-1]&&vis[daoyu[dao].id+1])//这个岛左边和右边都淹了                 {                     sum--;//那么这个孤岛淹了之后,总数-1                 }                 else if(!vis[daoyu[dao].id-1]&&!vis[daoyu[dao].id+1])//都没淹                 {                     sum++;//形成一个断层,+1                 }             }             vis[daoyu[dao].id]=1;             dao++;//判断下一个岛         }         ans[haipingmian[i].id]=sum;     }     for(long long i=1;i<=m;i++)     {         cout<<ans[i]<<endl;     } }

转载请注明原文地址: https://www.6miu.com/read-1400073.html

最新回复(0)