关于为什么环形石子归并可以将环当成链处理
注意:本文比较粗糙,待去锯齿、待优化模型、待优化上色。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
翻译过标题来就是为什么一个环形的n石子归并可以转化为n个链形的n石子归并
两种合并相同的特征有:
1.有n个石子(废话)
2.最后一步合并时总是 没 得 选
我能看出来的相同特征只有这 两个 一个,欢迎来访的客人在评论区补充。
正文:
在一次石子归并中,最后一次的合并一定发生在某两个区间中,这两个区间的长度和是初始时石子堆的个数。
由于这两个区间具有分明的界限,所以在此之前(此:最后一次合并),这两个区间的界限(一条空想的线)两旁的两个石子堆,只会有一种合并选择(当然不会只有一种选择),
这种合并行为性质和链合并中的链头和链尾的性质相同。
所以对于环形石子归并,可以将ta的过程以“最后合并的两个堆的界限”归类,分为n类,
每一类都可以用链状石子归并求解,所以,emmm……。

更多精彩