当前位置: 代码迷 >> 综合 >> 51nod 1276 岛屿的数量 思维好题
  详细解决方案

51nod 1276 岛屿的数量 思维好题

热度:21   发布时间:2024-01-15 06:23:36.0

1276 岛屿的数量

  1. 1.0 秒
  2.  
  3. 131,072.0 KB
  4.  
  5. 20 分
  6.  
  7. 3级题

有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}。

 收起

输入

第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)。

输出

输出共Q行,对应每个查询的岛屿数量。

输入样例

5 4
2
1
3
2
3
0
1
3
2

输出样例

1
2
0
2

 

我们对岛屿高度和询问的权值w都按照从小到大排序,因为这样就可以简单优化对w淹没的高度。

我们可以用一个vis数组来标记他是否被淹没,如果他本身和旁边的两个岛屿都每没有被淹没,才会减少一个岛屿数量。如果他本身和旁边的两个岛屿都每被淹没,增加一个岛屿数量

注意一下第一个位置和最后一个位置特判就可以。

哎,我的二分+树状数组竟然T了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 11;
int n,m;//元素个数struct Node
{int val;int index;
} a[N];
bool cmp1(Node x,Node y)
{if(x.val==y.val)return x.index<y.index;return x.val<y.val;
}
struct Option
{int w;int index;
} op[N];
bool cmp2(Option x,Option y)
{return x.w<y.w;
}
int ans[N];
int vis[N];
int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%d",&a[i].val);a[i].index=i;}sort(a+1,a+n+1,cmp1);for(int i=1; i<=m; i++){scanf("%d",&op[i].w);op[i].index=i;}sort(op+1,op+m+1,cmp2);int top=1;int res=1;for(int i=1; i<=m; i++){//cout<<"#"<<op[i].w<<endl;while(top<=n&&a[top].val<=op[i].w){//cout<<a[top].index<<" "<<a[top].val<<endl;if(a[top].index==n){if(vis[n-1]==1){res--;} }else if(a[top].index==1){if(vis[2]==1){res--;} }else if(vis[a[top].index-1]==0&&vis[a[top].index+1]==0){res++;}else if(vis[a[top].index-1]==1&&vis[a[top].index+1]==1)res--;vis[a[top].index]=1;top++;}ans[op[i].index]=res;}for(int i=1; i<=m; i++){printf("%d\n",ans[i]);}return 0;
}

 

 

T的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 11;
const int mod =  1e9 + 7;
//树状数组只能计算A[1]开始的和,A[0]这个元素是不能用的。
const int MAXN=100000+5;//最大元素个数
int n,m;//元素个数
int c[MAXN];//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
//返回i的二进制最右边1的值
int lowbit(int i)
{return i&(-i);
}
//返回A[1]+...A[i]的和
ll sum(int x)
{ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}//令A[i] += val
void add(int x, ll val)
{while(x <= n)   //注意这里的n,是树状数组维护的长度{c[x] += val;x += lowbit(x);}
}
struct Node
{int val;int index;
} a[N];
bool cmp1(Node x,Node y)
{if(x.val==y.val)return x.index<y.index;return x.val<y.val;
}
struct Option
{int w;int index;
} op[N];
bool cmp2(Option x,Option y)
{return x.w<y.w;
}
int ans[N];
int find_0(int pos)
{int l=pos,r=n;while(l<r){int mid=(l+r+1)>>1;if(sum(mid)-sum(pos-1)==0)l=mid;elser=mid-1;}return l; 
}
int find_1(int pos)
{int l=pos,r=n;while(l<r){int mid=(l+r+1)>>1;if(sum(mid)-sum(pos-1)==mid-pos+1)l=mid;elser=mid-1;}return l; 
}
int main()
{memset(c,0,sizeof(c));scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%d",&a[i].val);a[i].index=i;}sort(a+1,a+n+1,cmp1);for(int i=1; i<=m; i++){scanf("%d",&op[i].w);op[i].index=i;}sort(op+1,op+m+1,cmp2);int top=1;for(int i=1; i<=m; i++){//cout<<"#"<<op[i].w<<endl;while(top<=n&&a[top].val<=op[i].w){//cout<<a[top].index<<" "<<a[top].val<<endl;add(a[top].index,1);top++;}for(int t=1; t<=n;){if(sum(t)-sum(t-1)==0){ans[op[i].index]++;t=find_0(t)+1;}else{t=find_1(t)+1;}}//ans[op[i].index]=sum(op[i].r)-sum(op[i].l-1);}for(int i=1; i<=m; i++){printf("%d\n",ans[i]);}return 0;
}