Codeforces 1132C – Painting the Fence

题目链接:Codeforces 1132C

首先预处理所有的询问,统计每个段有多少个人涂,即对每个$[l_i, r_i]$区间加一。

我们需要$q-2$个人,反向考虑我们删掉哪两个。枚举删掉的第一个,把他的区间贡献从预处理的数组中删去,然后用一个新的数组$c$来记录哪些点只有一个人涂,即$c_i = [a_i = 1]$。接着我们去枚举除了第一个人之外的所有人,如果把他们删掉,那么会有多少个点变成0,即对$c_i$求前缀和,这个值为$pre[r_i] – pre[l_i – 1]$。我们希望这个值尽可能的小,因此最小的那个就是我们要删除的第二个点。

这种固定一个(枚举),求另一个的方法是一种常用方法。

时间复杂度$O(nq + q^2)$。

 

说点什么

avatar
50
  Subscribe  
提醒