bzoj1635[Usaco2007 Jan]Tallest Cow 最高的牛*

bzoj1635[Usaco2007 Jan]Tallest Cow 最高的牛

题意：

n头牛，知道所有牛身高不超过h，给出r条关系(a,b)表示第a+1到b-1头牛都比a，b牛矮，且a牛不必b牛高，问每头牛的最高身高。n≤10000，r≤10000。

题解：

那个“a牛不必比b牛高”的条件没什么用，且中间那些牛都比左右牛矮直接让它们比两边牛矮1即可。故用差分序列的方法sum[a+1]--,sum[b]++，然后将sum累加起来加上h即可。还有条件可能有重复的要判重。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <stack>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 10010
 7 #define ll long long
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 int h[maxn],n,k,m,r; struct ask{int a,b;}asks[maxn];
17 bool cmp(ask a,ask b){return a.a==b.a?a.b<b.b:a.a<b.a;}
18 int main(){
19     n=read(); k=read(); m=read(); r=read();
20     inc(i,1,r){int x=read(),y=read(); asks[i]=(ask){min(x,y)+1,max(x,y)-1};} sort(asks+1,asks+r+1,cmp);
21     inc(i,1,r){
22         if(asks[i].a==asks[i-1].a&&asks[i].b==asks[i-1].b)continue; h[asks[i].a]--; h[asks[i].b+1]++;
23     }
24     h[0]=m; inc(i,1,n)h[i]+=h[i-1],printf("%d
",h[i]); return 0;
25 }

20160923