首页 > 代码库 > bzoj1635[Usaco2007 Jan]Tallest Cow 最高的牛*
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\n",h[i]); return 0;25 }
20160923
bzoj1635[Usaco2007 Jan]Tallest Cow 最高的牛*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。