-
思路:
先不管最大高度,我们读入一对x,y.说明,x+1~y-1之间牛的身高都小于x,y。
然后不妨将这个区间打个标记-1。所有操作后,可知最高的那个牛它的标记一定是0,并且标记数量与身高排名正相关,于是再将所有奶牛的标记数加上最高身高h就是可能的最大身高。
因为之前的操作保证标记的数量是按着身高排名来的,加上最大身高当然是最大可能身高。
然后我们是要将x+1~y-1打标记,根据差分数组的思维,就要让x+1处-1,y处+1。
-
注意:
- 判重,用map,pair或hash。
- 可能读入x,y大小关系符的需要swap
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=10005;
int n,m,h,i;
int f[maxn],tp[maxn];
bool h_[19260817]; //暴力Hash需谨慎 逃)
bool m_hash(int x,int y)
{
int t=(x*y+x/y+x+y+(x>>1)-(y>>1))%19260817; +1s
if(h_[t])return 0;
else h_[t]=1;
return 1;
}
int main()
{
cin>>n>>i>>h>>m;
for(register int i=1;i<=m;i++)
{
register int a,b;
scanf("%d %d",&a,&b);
if(a>b)swap(a,b);
if(m_hash(a,b)){
tp[a+1]--,tp[b]++;
}
}
for(register int i=1;i<=n;i++)
{
f[i]=f[i-1]+tp[i];
cout<<f[i]+h<<endl;
}
return 0;
}