题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#define N 10010
using namespace std;
long d[N]; //初始差分数列为0,表示所有牛的身高没有差距,等于最高的牛h
int main()
{
int n,p,m,i,a,b;
long h;
cin>>n>>p>>h>>m; //n:牛的数量,m:能相互看到的牛的对数,h最高的牛的高度,p:最高的牛的位次
map<pair<int,int>,bool> exist; //保存某两头牛相互看见的关系是否存在
for(i=1;i<=m;i++)
{
cin>>a>>b; //a保存a,b序号中的最小值,b保存a,b序号中的最大值
if(a>b)
{
swap(a,b);
}
if(exist[{a,b}]) //如果a,b两头牛互相能看到的关系存在,则此次输入无效
{
continue;
}
//初始差分序列为
d[a+1]--; //a,b两头牛能互相看见,表示[a,b]区间内牛的身高至少比a和b矮1
d[b]++;
exist[{a,b}]=true; //标记a,b两头牛的关系已输入
}
for(i=1;i<=n;i++) //差分序列的前缀和序列表示每头牛比最高的牛矮多少
{
d[i]+=d[i-1];
cout<<d[i]+h<<endl;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla