岛
题目 岛
思路分析
思路见上一题 非零段划分
唯一的不同在于 数据范围变得更大
使得我们无法使用数组存下 在整个差分数组更新每个点状态修改后对答案的影响
最后再把所有元素构造前缀和 把所有时间点的岛数算出来
那么就得把数据离散化成比较小的范围 能够放得下 让我们可以用差分
即舍去一些用不到的元素
对于第一二种做法（从水平线入手） 可以发现
我们要用到的是只是去掉相邻相同元素的那些点
我们确实做了去重 但是实际上对答案有影响的也只是他们
我们没必要对整个数组做差分→前缀和 （算所有时间点的岛域数 找最大）
没用到的点都是0 差分中 0不构成任何影响
那么就把所有要用到的岛离散化出来
排序一下 从小到大或者从大到小去取出 每轮累加一下和
实际上和 做前缀和后缀和是一样的（细品）
这样就变成了 算每次淹没/露出这些关键时间点的岛屿数
当然 有个注意的点就是 如果存在
这样 处于同一水平面（不相邻所以不会被去重）的
他们处于同一个时刻 结果应该要在同一轮计算 而不能这一轮加了 下一轮减掉
（之前的前缀和方式是以时间为单位的 在该时间++ -- 最后再统一算 所以会平衡
而这里 是要每轮出答案 如果先加了 这个可能被当成最大的res保存了 显然有问题）
所以 我们在做的时候得进行一次判断 如果下一个点跟这一个点在同一水平位置
那我们这次就不更新答案
只有与下一个点不同时 才更新答案
对于第二种情况
跟我们平时做的离散化就更相似些了
我们本身就是在插入的时候进行差分操作
最后再把所有时间点求一次前缀和
但是现在这个for(1~10000）变成了1~\(10^9\)
不能这样做了
那么 可以直接把这些东西放在map里面 而不是一个数组里面
我们使用map来实现离散化 代替数组做差分
代码实现
从下往上
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n;
int h[N];
PII q[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
n=unique(h+1,h+n+1)-(h+1);
h[n + 1] = 0;
for(int i=1;i<=n;i++)
q[i]={h[i],i};
sort(q+1,q+n+1);
int res=1,cnt=1;
for(int i=1;i<=n;i++){
int k=q[i].second;
if(h[k-1]<h[k] && h[k+1]<h[k])
cnt--;
else if(h[k-1]>h[k] && h[k+1]>h[k])
cnt++;
if(q[i].first!=q[i+1].first)
res=max(res,cnt);
}
cout<<res<<endl;
return 0;
}
从上往下
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n;
int h[N];
PII q[N];
bool cmp(pair<int, int>a, pair<int, int>b)
{
return a.first>b.first;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
n=unique(h+1,h+n+1)-(h+1);
h[n + 1] = 0;
for(int i=1;i<=n;i++)
q[i]={h[i],i};
sort(q+1,q+n+1,cmp);
int res=0,cnt=0;
for(int i=1;i<=n;i++){
int k=q[i].second;
if(h[k-1]<h[k] && h[k+1]<h[k])
cnt++;
else if(h[k-1]>h[k] && h[k+1]>h[k])
cnt--;
if(q[i].first!=q[i+1].first)
res=max(res,cnt);
}
cout<<res<<endl;
return 0;
}
从点入手 差分 map实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010,M = 1e9+10;
int a[N];
map<int ,int >b;//用map代替数组 实现离散化的差分
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
if(a[i]>a[i-1]){
b[a[i-1]]++,b[a[i]]--;
}
}
LL sum = 0 ,res = 0;
for (auto i:b ){
sum+=i.second;
res = max(res,sum);
}
cout<<res<<endl;
}
从点入手 差分 手写离散化
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010,M = 1e9+10;
int a[N];
vector<int> alls;
int b[N];
int n;
int find(int x)
{
int l=0,r=alls.size()-1;
while(l<r){
int mid=l+r>>1;
if(alls[mid]>=x)
r=mid;
else
l=mid+1;
}
return r;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
alls.push_back(a[i]);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for (int i = 1; i <= n; i ++ ){
if(a[i]>a[i-1]){
b[find(a[i-1])]++,b[find(a[i])]--;
}
}
LL sum = 0 ,res = 0;
for (auto i:b ){
sum+=i;
res = max(res,sum);
}
cout<<res<<endl;
}
💬 评论