题目描述

北京曾有四道城墙环绕：紫禁城、皇城、内城和外城。这些城墙在 $20$ 世纪 $50$ 至 $60$ 年代大多被拆除以修建道路。城墙由守卫塔保护，每个塔内驻守一名守卫。城墙可以看作一个大环，每个守卫塔恰好有两个邻居。

守卫需要全天监视其负责的城墙段，因此必须留在塔内。这是一项非常枯燥的工作，因此保持守卫的积极性很重要。激励守卫的最佳方法是授予其大量奖项。有多种不同类型的奖项可以颁发：杰出服务奖、最佳制服奖、守卫大师奖、卓越视力奖等。城市守卫中央部门确定了每位守卫需要获得的奖项数量。一个奖项可以授予多名守卫。但需要注意：不应将同一奖项授予两个相邻的守卫，因为如果邻居已获得该奖项，守卫就无法以此为荣。任务是编写一个程序，确定需要多少种不同类型的奖项才能保持所有守卫的积极性。

输入格式

输入包含多个测试用例块。每个测试用例以一行包含单个整数 $1\le n\le 100000$ 开始，表示守卫塔的数量。接下来 $n$ 行对应 $n$ 个守卫：每行包含一个整数，表示该守卫需要的奖项数量。每个守卫至少需要 $1$ 个，最多需要 $100000$ 个奖项。守卫 $i$ 和 $i+1$ 是邻居，它们不能收到相同的奖项。第一个守卫和最后一个守卫也是邻居。

输入以 $n=0$ 的块终止。

输出格式

对于每个测试用例，输出一行包含一个整数，即允许我们激励守卫所需的最少奖项类型数 $x$。也就是说，如果我们有 $x$ 种类型的奖项，那么我们可以按照每个守卫的要求给予其尽可能多的奖项，并且我们可以确保相邻守卫不会获得相同类型的奖项。每个守卫从每种类型只能获得一个奖项。

样例输入

3
4
2
2
5
2
2
2
2
2
5
1
1
1
1
1
0

样例输出

8
5
3

题目分析

这是一个环形约束下的资源分配问题。我们需要在满足相邻守卫奖项类型互不相同的条件下，找到最小的奖项类型总数 $x$，使得每个守卫 $i$ 都能获得其所需的 $a[i]$ 个不同类型的奖项。

关键观察

1. 基本下界：奖项类型数 $x$ 至少为 $\max (a[i])$，因为单个守卫的需求必须满足。
2. 相邻约束：对于任意相邻的两个守卫 $i$ 和 $i+1$，由于它们的奖项集合必须完全不相交，因此有 $a[i]+a[i+1]\le x$。
3. 环形特性：由于守卫排列成环，第一个和最后一个守卫也是邻居，这增加了问题的复杂性。

解法思路

情况一：$n$ 为偶数

当守卫数量 $n$ 为偶数时，我们可以将守卫分成两组（奇数位置和偶数位置），每组内部没有相邻关系。此时，答案就是相邻守卫需求之和的最大值：

$$x=\max (\max (a[i]),\max (a[i]+a[i+1]))$$

其中 $a[n+1]=a[1]$ 以处理环形情况。

情况二：$n$ 为奇数

当 $n$ 为奇数时，问题变得更加复杂。我们采用二分答案结合贪心验证的方法：

1. 二分框架：在 $[maxAdjacentSum,\text{INF}]$ 范围内二分查找最小的可行 $x$，其中 $maxAdjacentSum$ 是相邻守卫需求之和的最大值。

2. 贪心验证：对于给定的 $x$，检查是否存在合法的奖项分配方案。

贪心验证算法详解

设总奖项类型数为 $x$，我们将奖项分为两个池：

• 相同池：与第一个守卫使用的奖项类型相同的池，大小为 $l=a[1]$
• 不同池：与第一个守卫使用的奖项类型不同的池，大小为 $r=x-a[1]$

定义：

• $sameAwards[i]$：第 $i$ 个守卫使用与第一个守卫相同的奖项数量
• $diffAwards[i]$：第 $i$ 个守卫使用与第一个守卫不同的奖项数量

显然有：$sameAwards[i]+diffAwards[i]=a[i]$

初始化

• $sameAwards[1]=a[1]$
• $diffAwards[1]=0$

交替分配策略

对于 $i=2$ 到 $n$：

• 当 $i$ 为奇数时：尽量多用"不同"奖项
  $$diffAwards[i]=\min (r-diffAwards[i-1],a[i])$$
  $$sameAwards[i]=a[i]-diffAwards[i]$$

• 当 $i$ 为偶数时：尽量多用"相同"奖项
  $$sameAwards[i]=\min (l-sameAwards[i-1],a[i])$$
  $$diffAwards[i]=a[i]-sameAwards[i]$$

正确性证明

这种交替分配策略的巧妙之处在于：

1. 约束自动满足：通过 $\min$ 操作确保不超过可用奖项池的大小限制
2. 相邻不相交：相邻守卫通过交替使用相同池和不同池，自然避免了奖项类型冲突
3. 环形处理：最后检查 $sameAwards[n]==0$，确保第 $n$ 个守卫与第 $1$ 个守卫没有相同的奖项类型

最终检查

验证 $sameAwards[n]==0$，因为第 $n$ 个守卫与第 $1$ 个守卫相邻，不能使用相同的奖项类型。

时间复杂度分析

• 贪心验证函数：$O(n)$
• 二分查找：$O(\log (\text{maxAnswer}))$
• 总复杂度：$O(n\log (\text{maxAnswer}))$，对于 $n\le 100000$ 是可接受的

代码实现

// Beijing Guards
// UVa ID: 1335
// Verdict: Accepted
// Submission Date: 2025-10-20
// UVa Run Time: 0.010s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 200010;

int awardsNeeded[MAX];    // 每个守卫需要的奖章数量
int sameAwards[MAX];      // sameAwards[i]: 第 i 个守卫使用与第 1 个守卫相同的奖章数量
int diffAwards[MAX];      // diffAwards[i]: 第 i 个守卫使用与第 1 个守卫不同的奖章数量
int guardCount;

// 检查奖章总数 totalAwards 是否足够分配给所有守卫
bool canAssignAwards(int totalAwards) {
    // samePool: 与第一个守卫相同的奖章池大小（等于第一个守卫需要的奖章数）
    // diffPool: 与第一个守卫不同的奖章池大小
    int samePool = awardsNeeded[1];
    int diffPool = totalAwards - awardsNeeded[1];
    // 初始化第一个守卫：全部使用"相同"奖章
    sameAwards[1] = awardsNeeded[1];
    diffAwards[1] = 0;
    // 为第 2 到第 guardCount 个守卫分配奖章
    for(int i = 2; i <= guardCount; i++) {
        if(i % 2 == 1) { 
            // 奇数下标的守卫：尽量多用"不同"奖章
            // 可用的不同奖章数 = 不同奖章池总数 - 前一个守卫使用的不同奖章数
            diffAwards[i] = min(diffPool - diffAwards[i-1], awardsNeeded[i]);
            sameAwards[i] = awardsNeeded[i] - diffAwards[i];
        }
        else { 
            // 偶数下标的守卫：尽量多用"相同"奖章  
            // 可用的相同奖章数 = 相同奖章池总数 - 前一个守卫使用的相同奖章数
            sameAwards[i] = min(samePool - sameAwards[i-1], awardsNeeded[i]);
            diffAwards[i] = awardsNeeded[i] - sameAwards[i];
        }
    }
    // 关键检查：第 guardCount 个守卫与第 1 个守卫相邻，不能有相同奖章
    // 所以 sameAwards[guardCount] 必须为 0（最后一个守卫不能使用任何与第 1 个守卫相同的奖章）
    return sameAwards[guardCount] == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin >> guardCount) {
        if(guardCount == 0) break;
        int maxAdjacentSum = 0;  // 相邻守卫需求之和的最大值
        // 读入数据并计算相邻需求之和的最大值
        for(int i = 1; i <= guardCount; i++) {
            cin >> awardsNeeded[i];
            // 计算当前守卫与前一个守卫的需求之和
            if(i > 1) {
                maxAdjacentSum = max(maxAdjacentSum, awardsNeeded[i] + awardsNeeded[i-1]);
            }
        }
        // 检查首尾两个守卫的需求之和（环形）
        maxAdjacentSum = max(maxAdjacentSum, awardsNeeded[1] + awardsNeeded[guardCount]);
        // 特殊情况处理
        if(guardCount == 1) {
            // 只有一个守卫，直接输出其需求
            cout << awardsNeeded[1] << endl;
            continue;
        }
        else if(guardCount % 2 == 0) {
            // 偶数个守卫：答案就是相邻需求之和的最大值
            // 因为可以将守卫分成两组交替分配奖章
            cout << maxAdjacentSum << endl;
            continue;
        }
        // 奇数个守卫：使用二分查找确定最小奖章数
        int low = maxAdjacentSum;      // 下界：相邻需求之和的最大值
        int high = INF;                // 上界：一个足够大的数
        // 二分查找
        while(low < high) {
            int mid = (low + high) / 2;
            if(canAssignAwards(mid)) {
                // mid 足够，尝试更小的值
                high = mid;
            }
            else {
                // mid 不够，需要更大的值
                low = mid + 1;
            }
        }
        // 输出最小奖章数
        cout << low << endl;
    }
    return 0;
}

总结

本题通过巧妙的贪心策略和二分查找，高效地解决了环形约束下的资源分配问题。交替使用相同池和不同池的分配方法确保了相邻守卫奖项类型不重复，同时最小化了所需的奖项类型总数。该算法在时间复杂度和空间复杂度上都能很好地处理题目给出的数据规模限制。