题目描述
有 N头牛站成一行,被编队为 1、2、3…N,每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。
现在,我们只知道其中最高的牛是第 P头,它的身高是 H,剩余牛的身高未知。
但是,我们还知道这群牛之中存在着 M对关系,每对关系都指明了某两头牛 A和B可以相互看见。
求每头牛的身高的最大可能值是多少。
样例
9 3 5 5
1 3
5 3
4 3
3 7
9 8
5
4
5
3
4
4
5
5
5
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10001;
int t[N]; //差分数组
bool st[N][N]; //用于判断操作是否重复
void insert(int l,int r,int c) //在[l,r]上增加一个数c
{
t[l]+=c;
t[r+1]-=c;
}
int main()
{
int n,p,h,m;
cin>>n>>p>>h>>m;
t[1]+=h; //初始化让所有牛的身高都等于最大身高
while(m--)
{
int a,b;
cin>>a>>b;
if(a>b)swap(a,b); // 让a的值小于b的值,因为在区间添加时 l<r
if(b-a==1)continue; //判断俩个牛是否相邻,相邻就可以跳过了
if(!st[a][b]) //如果是第一次操作这两头牛
{
insert(a+1,b-1,-1); //这里让俩头牛之间的牛的身高减一,对应的区间为[l+1,r-1];
st[a][b]=st[b][a]=true;
}
}
for(int i=1;i<=n;i++)
{
t[i]+=t[i-1]; //求一下前缀和,即牛的身高
cout<<t[i]<<endl;
}
return 0;
}