[POJ3263][洛谷P2879][USACO07JAN]区间统计Tallest Cow[差分]

题面

根据贪心的思路, 两头牛a,b能相互看见, 一定有区间[a+1,b-1]内的牛比它们至少小1. 因此建立一个初值全为0的数组d, 每读入一对关系a,b, 就把区间d[a+1,b-1]全部减一. 当所有关系读入完毕, 数组d内就是牛之间的相对高度差. 用已知的最高牛i的身高h加上这个高差, 就可以得到每头牛的最大身高.

问题是区间内数值逐个修改复杂度太高, 有$latex O(NM)$, 所以这里引入差分的概念(用线段树可以水过).设差分数组$latex c[i]=d[i]-d[i-1]$, 则有$latex c[i]=\sum_{j=1}^{i}d[j]$. 当区间[x,y]都加上或减去同一个数时, c[x+1]~c[y]都不变,只要修改c[x]和c[y+1]即可.这样就成功的把对一个区间的修改转化为了对两端点的修改.

注意关系可能重复给出, 要用map判重.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址