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; } }