题目传送门
【题目大意】
有$N$头奶牛站成一行，给出最高的奶牛身高$H$及其编号，已知$M$对关系，即第$i$头奶牛能看见第$j$头奶牛时，满足条件：
1.第$j$头奶牛的身高不小于第$i$头奶牛
2.假定$j<i$，则从$j+1$到$i-1$之间的每一头奶牛身高都小于第$i$头奶牛且小于第$j$头奶牛
求每个奶牛可能的最高身高。
【思路分析】
我个人的思路是这样的，所有奶牛的初始身高为最高身高，已知第$i$头奶牛能看见第$j$头奶牛且$j<i$，则
$$h[j]=max(h[j],h[i])$$
$$for(int x=j+1;x<i;x++)h[x]--;$$
把$M$个关系正循环一遍，反循环一遍，然后输出……就over。
据说正解是前缀和，我也讲一下吧，是这样的，设一个数组$c[i]$表示奶牛$i$身高与最高身高的差值，即最后的答案为$H+c[i]$。对于每一个关系中的$i$和$j$(假定$j<i$)，把$c$数组中下标为$j+1$到$i-1$的数都减１。但是这样复杂度太高(据说有$O(MN)$)，于是我们用一个$d$数组来转化一下，$d[j+1]--;d[i]++$，表示“身高减１”的影响从$j+1$开始，持续到$i-1$，到$i$结束。最后，$c$数组的值等于$d$数组的前缀和，即
$$c[x]=\sum_{y=1}^{x}d[y]$$
【代码实现】
1 #include<iostream> 2 #include<cstdio> 3 #define rg register 4 #define go(i,a,b) for(rg int i=a;i<=b;i++) 5 #define back(i,a,b) for(rg int i=a;i>=b;i--) 6 using namespace std; 7 const int N=10002; 8 int n,I,H,m; 9 int h[N],a[N],b[N]; 10 int main(){ 11 scanf("%d%d%d%d",&n,&I,&H,&m); 12 go(i,1,n) h[i]=H; 13 go(i,1,m){ 14 scanf("%d%d",&a[i],&b[i]); 15 int A=a[i],B=b[i]; 16 if(h[A]>h[B]) h[B]=h[A]; 17 if(A>B) swap(A,B); 18 go(j,A+1,B-1) h[j]=min(h[A],h[B])-1; 19 } 20 back(i,r,1){ 21 int A=a[i],B=b[i]; 22 if(h[A]>h[B]) h[B]=h[A]; 23 if(A>B) swap(A,B); 24 go(j,A+1,B-1) h[j]=min(h[A],h[B])-1; 25 } 26 go(i,1,n) printf("%d\n",h[i]); 27 return 0; 28 } 我的玄学代码 1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #define rg register 5 #define go(i,a,b) for(rg int i=a;i<=b;i++) 6 #define back(i,a,b) for(rg int i=a;i>=b;i--) 7 using namespace std; 8 const int N=10002; 9 map<pair<int,int>,bool> existed; 10 int c[N],d[N]; 11 int main(){ 12 int n,p,H,m; 13 scanf("%d%d%d%d",&n,&p,&H,&m); 14 go(i,1,m){ 15 int a,b; 16 scanf("%d%d",&a,&b); 17 if(a>b) swap(a,b); 18 if(existed[make_pair(a,b)]) continue; 19 d[a+1]--;d[b]++; 20 existed[make_pair(a,b)]=1; 21 } 22 go(i,1,n){ 23 c[i]=c[i-1]+d[i]; 24 printf("%d\n",H+c[i]); 25 } 26 return 0; 27 } 正解代码转载于:https://www.cnblogs.com/THWZF/p/11245065.html
相关资源：JAVA上百实例源码以及开源项目