【差分】积木大赛
/ / 点击 / 阅读耗时 2 分钟原题链接
思路
看到区间上加减同一值的操作,容易想到使用差分预处理。原问题变成,如何通过(+1,-1)
的成对操作,使得数组中所有数字变成0。
一个直观的策略是,对于每一个负数,我们应该通过其之前的正数将其抵消。根据差分的定义,,而,故而对于任何一个负数,一定可以找到一系列正数来与之抵消,我们的方法是合法的。其次,无论是哪一种方法,至少都需要将其中每一个负数变成正数,故而我们的方法是最优的。
实现
1 |
|
感谢阅读!欢迎评论嗷~
看到区间上加减同一值的操作,容易想到使用差分预处理。原问题变成,如何通过(+1,-1)
的成对操作,使得数组中所有数字变成0。
一个直观的策略是,对于每一个负数,我们应该通过其之前的正数将其抵消。根据差分的定义,,而,故而对于任何一个负数,一定可以找到一系列正数来与之抵消,我们的方法是合法的。其次,无论是哪一种方法,至少都需要将其中每一个负数变成正数,故而我们的方法是最优的。
1 |
|