基础方法の思路分析
糖糖别胡说,我真的不是签到题目
http://www.nowcoder.com/questionTerminal/9d5b203a30bc4e7b85f1838d60cf2236
私の初始思路:
1.对每个点往前搜,满足条件的被消灭,这是个n方的算法。
2.用delta数组维护发功会增加的部分,思路是对的但是可以观察区间的特征来描述
为什么不好?
应为最常见的模拟思路是把时间看做变量,把每个时间上发生的事情都原本重复。
解题思路:(发现数学规律消除时间的影响,不要重复操作)
1.这里发功的维护有一个特点就是左端点是固定的,所以可以录入sum[i]表示第i秒时,进行了发功,对sum做了一次前缀和之后,sum[i]代表第i秒时一共加了sum[i]次,任意一个点在i秒时加了几次都可以算出来
例如对于点2,就用sum[i]-sum[1]来表示,末尾的i就代表现在是第几秒。
下面论证在过程中被消灭和最后被消灭没有区别,
b[j]+sum[j]−sum[j−1]>b[i]+sum[j]−sum[i−1],第j秒时想要删掉不同组的i要满足如上条件,
化简b[j]−sum[j−1]>b[i]−sum[i−1]
很明显这和时间已经没有关系了,所以只要最后处理一次就好了。
算出最终时刻每个点的d[i]=b[i]-sum[i-1]然后删一次就好