题目描述:
1276 岛屿的数量
有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 4213230132
思路:
先不考虑边界细节,每去掉一个 谷 峰,岛屿数量减少一个,每 去掉一个 谷底,岛屿数量增加 一个。
所以对于每次查询,就是寻找比当前查询高度小的谷底和谷峰数量,对本题而言,O(q*N)的复杂度显然超时,
所以可以对查询以及谷峰底序列排序,离线查询,遍历查询序列,用过的谷峰底不再用,时间复杂度O(Q+N+QlogQ
+NlogN)。
然后边界处理1和n的位置,可以发现当a【1】>a【2】、a【n】>a【n-1】时,是可以当作谷锋处理的。
特殊情况的处理即没有谷峰和谷底的时候,即高度全一样或者单调,此时特判即可。
代码实现:
#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<cstdio>#include<algorithm>#define LL long long#define INF 0x3f3f3f3fusing namespace std;const int N=2e5+100;int arr[N];pair<int,int>pek[N];int tot;pair<int,int> query[N];int ans[N];int main(){int n,q;while(cin>>n>>q){int maxs=INF;for(int i=1;i<=n;i++)cin>>arr[i],maxs=max(maxs,arr[i]);for(int i=2;i<n;i++){if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])pek[++tot]=make_pair(arr[i],1);if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])pek[++tot]=make_pair(arr[i],0);}if(tot==0||n==1){for(int i=1;i<=q;i++){int x;cin>>x;if(x>=maxs)ans[i]=0;else ans[i]=1;}for(int i=1;i<=q;i++)cout<<ans[i]<<endl;continue;}if(arr[1]>arr[2])pek[++tot]=make_pair(arr[1],1);if(arr[n]>arr[n-1])pek[++tot]=make_pair(arr[n],1);//for(int i=1;i<=tot;i++)cout<<pek[i].first<<" "<<pek[i].second<<endl;for(int i=1;i<=q;i++){cin>>query[i].first;query[i].second=i;}sort(query+1,query+1+q);sort(pek+1,pek+1+tot);int num1=0,num2=0;int p=1;for(int i=1;i<=q;i++){while(pek[p].first<=query[i].first&&p<=tot){if(pek[p].second==0){num2++;}else num1++;p++;}ans[query[i].second]=1+num2-num1;}for(int i=1;i<=q;i++)cout<<ans[i]<<endl;}return 0;}