思路

用差分数组记录第i头牛与第i-1头牛的身高差

再使用(前缀和累加+最大值)求最大可能值

易错点1：当编号a大于编号b时，交换两者位置

易错点2：注意去重，可以使用map数据结构(本题的l,r最大为R≤10000) 部分代码

    if(重复){
		continue;
   }else{
		差分数组[l+1]--;//第l+1头牛比第l头牛矮，差值-1 
		差分数组[r]++;//第r头牛比第l头牛高，第l头牛大于[l+1,r-1]区间内的牛 
		标记去重
		}

题意

有n只牛，第i只高度为h(最高)；

给出a和b，其中a,b之间的所有奶牛的高度都比a小

问n只牛的最大高度

思路

先假设每只牛的高度都是最高，再将(a,b]（从a+1到b）内的牛身高全部-1 （可以用差分优化）

然后没了

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

int n,I,h,r,a,b;
int f[10005];	//奶牛身高的差分数组
bool used[10005][10005];

int main(){
	cin>>n>>I>>h>>r;
	f[1]=h;
	while(r--){
		cin>>a>>b;
		if(!used[a][b]){	
			f[min(a,b)+1]--;	//f[a+1] 到 f[b] 全部减一
			f[max(a,b)]++;
		}
		used[a][b]=1;	//去重
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=f[i];
		cout<<ans<<'\n';
	}
	return 0;
}
}

需注意K组数据可能有重复，要特判一下