csp-非零段划分-差分前缀和-unique用法
问题描述:(贴图贴贴贴!)
问题分析:
对于暴力破解的方法不做过多描述: 202109-2 非零段划分_bulibuli蛋的博客-CSDN博客_非零段划分
前缀和 差分 可以先去这里面看看: 出行计划-差分前缀和_fz_orb的博客-CSDN博客
1.岛屿法解决问题:
考虑p足够大的情况,这时所有的岛都被海水淹没了,只有0个岛屿
然后海平面逐渐下降,岛屿数量开始变化
每当一个凸峰出现,岛屿数就会多一个;
每当一个凹谷出现,原本相邻的两个岛屿就被这个凹谷连在一起了,岛屿数减少一个
可以使用数组cnt[],cnt[i] 表示海平面下降到i时,岛屿数量的变化(++或者--)
这样,数组元素cnt[i]中存储的就是该元素被替换为0时,划分数变化的差分值
最大值则只需要从其”前缀和”(程序中实际为后缀和)中找出最大值。
附上图解:(这个图不是我画的) 找不到原来那个博主了 抱歉>>>>
1.1 源码:
/*
id:图图就爱怼老师
qq:q6-7212422
*/
int main()
{
int n, m;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d", a+i);
a[0] = a[n+1] = 0; //边界默认为0
n = unique(a, a+n+2) - a; //去掉相邻重复元素
for(int i=1; i<n-1; i++)
if(a[i-1]<a[i] && a[i]>a[i+1]) //凸峰
cnt[a[i]]++;
else if(a[i-1]>a[i] && a[i]<a[i+1]) //凹谷
cnt[a[i]]--;
// 因去重,不存在等于左右情况
int ans=0, sum=0;
for(int i=10000; i>0; i--) {
sum += cnt[i]; //差分的后缀和即为答案
ans = max(ans,sum);
}
printf("%d\n",ans);
}
1.2需要注意的地方:
关于unique函数:
2.差分前缀和(有点抽象)
使用数组cnt[],cnt[i] 表示p从i-1上升到i时,非零段数量的变化
那么则有:
如果 a[i]>a[i−1]
意味着当p取到 a[i−1]+1 到 a[i]之间的值时,非零段数目+1 (首先因为两端都是0 一定会落回0,那么只要上升了就会冒出来至少一个山头) (脑袋里肯定有一个画面了)
现在把那个画面扔掉,去考虑数组上的画面:
对于一个a[i]>a[i-1]就会让一个区间的所有值+1 (理所当然 大声喊出来:差分-前缀和!!!!!)
那么对于所有的a[i] 就会出现一堆叠加的区间,那我们的答案不就是 最高的那个叠加区间嘛!!!!!
从 正向前缀和数组 中找出最大值就是所要的结果,而且 小有意思的是 这个前缀和数组 最后一定全部都是0 (因为 差分数组 左边界+1 就会对应右边界-1 到最后体现在前缀和上 最后的最后肯定都是一串0啦!)
总结说来就是p的选择使得cnt[]"连续"的1越来越多,也就是叠加的区间越来越高!
2.1源码:
#include <iostream>
using namespace std;
const int N = 500005;
const int M = 10000;
int a[N], cnt[N];
int main()
{
int n, phrase = 0; // 整数个数,段数
int i;
cin >> n;
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if(a[i] > a[i-1])
{
//差分,p取a[i-1]+1~a[i]的非零段数量加一
cnt[a[i-1]+1]++;
cnt[a[i]+1]--;
}
}
int sum = 0;
for(i = 1; i < M; i++)
{
sum += cnt[i];
phrase = max(phrase, sum);
}
cout << phrase;
return 0;
}
还不懂的 再去看这个文章: 出行计划-差分前缀和_fz_orb的博客-CSDN博客
CSDN-Ada助手: 推荐 Python入门 技能树:https://edu.csdn.net/skill/python?utm_source=AI_act_python
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天值得看】榜单,全部的排名请看 https://bbs.csdn.net/topics/619179570。
不买Huracan不改名: 就在九龙湖校区
hold?study:games: “你只要使用一些xxxx,然后就能优营了,你懂的~” 这是啥啊,多跟老师联系吗?
m0_61874187: 想问一下,软件学院搬到南京哪了啊。