一、题意重述（清晰版）

给定长度为 $n$ 的数组 $a$，元素范围 $[1,w]$，$w\ge2$。

操作规则： 选择一对相邻且相等的元素 $a_i,a_{i+1}$，将它们修改为 $[1,w]$ 内的两个数，修改后必须不相等。 可操作任意次。

求两个答案：

1. 数组能达到的最大总和
2. 达到最大总和所需的最少操作次数

---

二、核心结论（解题关键）

这道题的最大和是固定的，只有两种可能：

1. 若数组已经可以变成全 $w$：最大和 $= n \times w$
2. 否则：最大和 $= n \times w - 1$

原因：

• 操作要求修改后的一对数必须不等
• 因此数组不可能全为 $w$（所有相邻都相等，无法通过操作满足约束）
• 能达到的最大值就是：除了一个位置是 $w-1$，其余全是 $w$，总和为 $n\cdot w -1$

---

三、完整分类讨论（对标标程）

我们按顺序处理所有情况：

情况 1：$n=1$

没有相邻元素，无法操作。

• 最大和：$a_1$
• 操作次数：$0$

---

情况 2：数组中所有元素都是 $w$

此时相邻元素全相等，但我们无法把它们改成全 $w$（违反操作后不等的约束）。 但标程中这一分支是：如果数组最小值就是 $w$（全 $w$）

• 最大和：$n\cdot w$
• 操作次数：$0$

---

情况 3：$w=2$（特殊值，单独处理）

$w=2$ 时，能取的最大值就是 $2$，约束极强：

• 理想最大和：$2n$
• 但因为不能有相邻相等，连续的 $1$ 会让总和被迫减 1
• 操作次数 = 连续相同段的长度贡献

标程直接遍历连续段计算答案。

---

情况 4：数组没有任何相邻相等元素

无需任何操作，直接输出原数组和，操作次数 $0$。

---

情况 5：通用情况（$w>2$，数组有相邻相等，无法全 $w$）

1. 最大和固定为：$\boldsymbol{n\cdot w - 1}$
2. 目标：计算让数组变成「几乎全 $w$，仅一个位置为 $w-1$」的最少操作次数

这是标程最核心的计算部分。

---

四、标程核心逻辑解析

1. 最大和直接输出

printf("%lld ", 1ll * w * N - 1);

2. 最优目标形态

我们要把数组变成： 绝大多数位置是 $w$，只有一对相邻位置是 $(w-1,w)$ 或 $(w,w-1)$ 这是满足约束的最大和形态。

3. 最少操作次数计算

标程做了两件关键的事：

1. 预处理两端连续的 $w$ 头部/尾部连续的 $w$ 不需要操作，直接跳过。
2. 遍历数组，找到最优的「断点位置」 断点就是放置 $w-1$ 的位置，让修改代价最小。
3. 翻转数组再遍历一次 统一处理左右对称的情况，简化代码。
4. 统计连续 $w$ 的段长，计算最小操作数。

---

五、标程代码逐段解释

#define MAXN 200005
int a[MAXN];

固定数组大小，满足 $n\le 2\times 10^5$。

---

1. 输入 + 边界 $n=1$

int N, w; scanf("%d%d", &N, &w);
for (int i = 1; i <= N; ++i) scanf("%d", a + i);
if (N == 1) return (void)printf("%d 0\n", a[1]);

$n=1$ 直接输出原值。

---

2. 全为 $w$ 的情况

if (*std::min_element(a + 1, a + N + 1) == w)
    return (void)printf("%lld 0\n", 1ll * w * N);

最小值 = $w$ → 全是 $w$，直接输出最大和。

---

3. 特殊处理 $w=2$

if (w == 2) {
    int ans = N * 2, pans = 0;
    for (int i = 1, j = 1; i <= N; i = ++j) if (a[i] == 1) {
        --ans; while (j < N && a[j + 1] == 1) ++j; pans += j - i;
    }
    return (void)printf("%d %d\n", ans, pans);
}

$w=2$ 时，连续 $1$ 会让总和 $-1$，同时统计操作次数。

---

4. 无相邻相等，无需操作

bool flag = true;
for (int i = 1; i < N; ++i) if (a[i] == a[i + 1]) flag = false;
if (flag) return (void)printf("%lld 0\n", std::accumulate(a + 1, a + N + 1, 0ll));

---

5. 通用情况：输出最大和 $n\cdot w -1$

printf("%lld ", 1ll * w * N - 1);

---

6. 已经是最优和，操作次数 0

if (std::accumulate(a + 1, a + N + 1, 0ll) == 1ll * w * N - 1)
    return (void)puts("0");

---

7. 核心：计算最少操作次数

int ans = 0x3f3f3f3f;
int l = (a[1] == w ? 2 : 1);
int r = (a[N] == w ? N - 1 : N);

• ans：最小操作次数，初始无穷大
• l/r：跳过首尾连续的 $w$（无需操作）

if ((a[1] == w && a[2] == w) || (a[N] == w && a[N - 1] == w)) {
    int Lw = 0, Rw = N + 1;
    while (a[Lw + 1] == w) ++Lw;
    while (a[Rw - 1] == w) --Rw;
    int pans = Rw - Lw;
    for (int i = Lw + 1, j = i; i < Rw; i = ++j)
        if (a[i] == w) {
            while (j + 1 < Rw && a[j + 1] == w) ++j;
            pans += (i == j ? 2 : ((j - i) >> 1) + 1);
        }
    ans = pans, l = Lw + 1, r = Rw - 1;
}

处理两端连续 $w$ 的极端情况，计算基础操作次数。

for (int d = 0; d < 2; std::reverse(a + l, a + r + 1), ++d) 
    for (int i = l - 1, pre = 0, len = 0; i + 2 <= r; ) {
        if (a[i + 1] == a[i + 2]) 
            ans = min( ... , ans);
        ++i;
        if (a[i] == w) ++len, pre += ...;
        else len = 0;
    }

• 循环 $2$ 次：正序 + 倒序，统一处理左右对称
• 遍历所有相邻相等对，找到操作次数最少的断点
• 动态维护连续 $w$ 长度，计算最优代价

最后输出最小操作次数 ans。

---

六、样例解释

样例 1

5 8
1 2 3 4 5

无相邻相等 → 输出原和 $15$，操作次数 $0$。

样例 2

7 5
3 1 2 3 4 1 1

最大和 $7\times5-1=34$。 标程计算出最少操作次数为 $6$，与样例输出一致。

---

七、时间复杂度

• 每组用例：$O(n)$
• 总 $n$ 之和 $\le 10^6$
• 完全满足 $2$ 秒时限

---

八、总结

1. 最大和只有两种：$n\cdot w$ 或 $n\cdot w -1$
2. 全 $w$ 无法达到 → 最大和为 $n\cdot w-1$
3. 最少操作次数 = 找到最优断点，把数组改成「几乎全 $w$」
4. 标程用正序+倒序遍历优雅地处理了所有对称情况