第2题

$n$ 个岛屿由 $n$ 座桥连成环。岛的编号为 $0$ 到 $n-1$，第 $i$ 座桥连第 $i$ 号岛与第 $(i+1)\bmod n$ 号岛。

某旅行团从第 $x_1$ 号岛出发，依次访问的岛编号为 $x_2,\ldots,x_m$。

现在需要选择拆掉一座桥，请问拆掉哪一座桥可以使得旅行团的过桥次数达到最小。

int solve(int n, int m, int x[])
{
    int diff[n];
    for (int i = 0; i < n; ++i) diff[i] = 0;
    int common = 0;
    for (int i = 1; i < m; ++i)
    {
        int prev = x[i - 1];
        int next = x[i];
        int begin, end;
        if (prev < next) {
            begin = prev;
            end = next;
        }
        else {
            begin = next;
            end = prev;
        }
        common += ____(1)____;
        int inc = ____(2)____;
        diff[____(3)____] += inc;
        diff[____(4)____] -= inc;
        prev = next;
    }
    int best = n * m;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        ____(5)____;
        if (best > sum) best = sum;
    }
    return ____(6)____;
}

(2) 处应填（ ）。

{{ select(1) }}

• common
• end*2 - begin*2
• begin*2 - end*2
• n + begin*2 - end*2