[无link]
对于该策略证明：
1 如果只比较一次，显然
2 如果比较了k次，证明两个串前k个元素是相同的，第k+1个元素不同，那么我选择1-k-1中任何一个位置开始比较，答案都不会更优，因为如果新串第K+1个元素更大，那么显然K+1个元素会大于1-k的元素，那么显然以k+1开头更有可能更优，如果第K+1个元素更小，那么显然从中间截出来的串甚至比新串还小。
项链游戏
发布时间 2023-11-09 09:43:41作者: Simex
[无link]
对于该策略证明：
1 如果只比较一次，显然
2 如果比较了k次，证明两个串前k个元素是相同的，第k+1个元素不同，那么我选择1-k-1中任何一个位置开始比较，答案都不会更优，因为如果新串第K+1个元素更大，那么显然K+1个元素会大于1-k的元素，那么显然以k+1开头更有可能更优，如果第K+1个元素更小，那么显然从中间截出来的串甚至比新串还小。