Lost Cows(线段树)

2017年10月15日490

3:Lost Cows

  1. 对问题的分析设计过程

    考虑拥有最小代号的奶牛所在的位置,可以发现其一定位于最右侧的计数器为0的位置上。然后考虑将其移出队列,位置比他大的位置的计数器都会减一,可以以此类推求出其他奶牛的代号。

    若将移出队列变成将其计数器变为$\infty$,则该题变成了支持序列的如下操作:

    • 找区间最小值所在位置
    • 区间减法
    • 单点修改

    即可用线段树来解决此问题。

  2. 程序中用到的数据机构和算法

    本程序使用带懒标记的线段树实现。详细原理请参考第一题。

  3. 程序的运行情况

    该程序提交了一次即通过

    1507796908309

  4. 在实习过程中得到的经验和体会

    线段树的写法需要形成自己的风格,才能提高速度与准确性。

Code:

 

%d 博主赞过: