最高的牛
首先我们来了解一下本题的核心算法————差分:
顾名思义,差分就是表示两个相邻数字的差
用数组可以表示成这样:
$b[i]=a[i]-a[i-1]$
这种算法可以使连续数列一起加减变成只修改两个变量
言归正传
这道题,我们可以用一个数组$C$来存身高,$C[i]$表示第$i$头牛的最大身高
之后通过读题和一点点的推导,
我们可以得到两个规律:
假设$a,b$两头牛可以相互看见
1.$C[a]=C[b]>C[a+1],C[a+2]..C[b-1]$
2.$C[a+1],C[a+2]..C[b-1]$比$a,b$两头牛看不见时多一
证明:
第一条是从题目条件得来的
第二条:
首先$C[a+1],C[b-1]$最大也只能比$C[a],C[b]$少一
之后$C[a+2]$到$C[b-2]$也会受到$C[a],C[b],C[a+1],C[b-1]$的影响少一
所以有了上面的规律,第一种方法就出来了——朴素算法!
每次给出$a,b$两头牛,就把$C[a+1]$到$C[b-1]$全部减一
最后再把最高的身高加上就行了
但再一看时间复杂度……
就无了……
那有什么算法能使时间复杂度减“一些”呢?
我们发现,本题中有连续数列一起加减的地方,
与前面提到的差分不谋而合
于是,我们就可以把暴搜减一的地方改成差分
正解他不就出来了吗?
注:给的$a,b$可能会重复,所以我们还要开一个$map$判断重复
正解代码
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> s;
int C[1000000],n,m,p,h;
int main()
{
cin>>n>>p>>h>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x>y){
int t=x;
x=y;
y=t;
}
if(s[make_pair(x,y)]==1) continue;//判断重复
C[x+1]--;
C[y]++;//差分
s[make_pair(x,y)]=1;//标记
}
for(int i=1;i<=n;i++){
C[i]+=C[i-1];
cout<<C[i]+h<<endl;
}
return 0;
}