一、问题分析与数学建模

1.1 问题本质

这是一道模拟 + 贪心 + 数学性质的综合问题，核心在于理解汇款操作的本质并找到判定可行性的充要条件。

问题形式化

给定：

• $N$ 个房子围成环形，编号 $1, 2, \ldots, N$
• 初始金额 $A[1..N]$，目标金额 $B[1..N]$

汇款规则：

• 房子 $i$ 可以向房子 $(i \bmod N) + 1$ 汇款 $x$ 元（$x$ 为整数）
• 汇款成本：房子 $i$ 减少 $2x$ 元（汇款 $x$ + 手续费 $x$）
• 汇款收益：下一个房子增加 $x$ 元

目标：判断能否通过一系列汇款操作，使得所有房子的金额从 $A[i]$ 变为 $B[i]$。

---

1.2 核心数学观察

观察 1：差值的定义

定义差值 $d[i] = A[i] - B[i]$，表示房子 $i$ 当前比目标多出的金额。

• $d[i] > 0$：房子 $i$ 有多余的钱
• $d[i] = 0$：房子 $i$ 恰好达到目标
• $d[i] < 0$：房子 $i$ 缺少钱

关键性质：汇款操作改变差值的方式。

---

观察 2：汇款操作的本质

设房子 $i$ 向房子 $j = (i \bmod N) + 1$ 汇款 $x$ 元，则：

$$\begin{cases} A[i] \leftarrow A[i] - 2x \\ A[j] \leftarrow A[j] + x \end{cases} $$

对应的差值变化：

$$\begin{cases} d[i] \leftarrow d[i] - 2x \\ d[j] \leftarrow d[j] + x \end{cases} $$

关键洞察：

• 房子 $i$ 的差值减少 $2x$（成本加倍）
• 下一个房子的差值增加 $x$（传递一半）

---

观察 3：贪心策略的合理性

引理 1：如果 $d[i] > 0$，汇款金额应该选择 $x = \lfloor d[i] / 2 \rfloor$。

证明：

• 目标是让 $d[i]$ 尽可能接近 0
• 汇款 $x$ 元后，$d[i]$ 变为 $d[i] - 2x$
• 为了让 $d[i] - 2x \approx 0$，应选择 $x \approx d[i] / 2$
• 由于 $x$ 必须是整数，取 $x = \lfloor d[i] / 2 \rfloor$

结果：

• 如果 $d[i]$ 是偶数，汇款后 $d[i] = 0$
• 如果 $d[i]$ 是奇数，汇款后 $d[i] = 1$

---

观察 4：收敛性分析

引理 2：每轮操作后，所有差值的最大值严格递减或保持不变，但不会持续不变。

证明： 设当前最大差值为 $M = \max_i d[i]$。

情况 1：$M$ 是偶数

• 差值为 $M$ 的房子汇款 $M/2$ 后，差值变为 0
• 下一个房子差值最多增加 $M/2 < M$
• 因此新的最大差值 $< M$

情况 2：$M$ 是奇数

• 差值为 $M$ 的房子汇款 $(M-1)/2$ 后，差值变为 1
• 下一个房子差值最多增加 $(M-1)/2 < M$
• 如果所有房子都是奇数差值且都为 $M$，则传递后可能保持 $M$
• 但在环形结构中，通过多轮传递，差值会逐渐减小

推论：算法会收敛到最大差值 $< 2$ 的状态。

---

观察 5：最终状态的判定

当最大差值 $< 2$（即所有 $d[i] \in \{0, 1\}$）时，无法再进行有效汇款（因为 $\lfloor 1/2 \rfloor = 0$）。

此时有三种可能的最终状态：

状态 1：所有 $d[i] = 0$

• 说明所有房子都达到目标 → 可行

状态 2：存在某些 $d[i] = 1$，其余 $d[i] = 0$

• 这些多余的 1 元无法消除 → 不可行

状态 3：所有 $d[i] = 1$

• 这是一个特殊情况，需要进一步分析

---

1.3 特殊状态的深入分析

定理 1：所有房子都多 1 元的可行性

命题：如果所有 $d[i] = 1$，则可行当且仅当存在至少一个 $B[i] > 0$。

证明（充分性）：

假设所有 $d[i] = 1$，即 $A[i] = B[i] + 1$ 对所有 $i$ 成立。

情况 1：所有 $B[i] = 0$

• 则所有 $A[i] = 1$
• 任何汇款 $x \ge 1$ 都会让某个房子的金额减少至少 2
• 无法让所有房子同时达到 0 → 不可行

情况 2：存在 $B[i] > 0$

• 则对应的 $A[i] = B[i] + 1 \ge 2$
• 可以构造如下汇款方案：

考虑房子按环形顺序 $1, 2, \ldots, N, 1, 2, \ldots$

构造方案：

1. 找到任意一个 $B[i] > 0$ 的房子，记为 $k$
2. 从房子 $k$ 开始，按逆序进行特殊汇款

具体构造较为复杂，但核心思想是：

• 利用 $A[k] \ge 2$ 的事实，可以进行至少一次汇款
• 通过精心设计汇款顺序，让多余的 1 元在环中"抵消"

数学原理： 当所有房子都多 1 元时，总共多了 $N$ 元。在环形结构中，如果至少有一个房子的期望 $> 0$，可以通过巧妙的汇款顺序，利用手续费机制逐步消除这 $N$ 元多余。

关键在于：手续费的"损耗"可以被精确控制，使得最终正好消除所有多余的 1 元。

证明（必要性）： 如果所有 $B[i] = 0$，则所有 $A[i] = 1$。

假设可行，则存在汇款序列使得最终所有房子金额为 0。

考虑第一次汇款：

• 必须有某个房子 $i$ 汇款 $x \ge 1$
• 则 $A[i]$ 减少 $2x \ge 2$
• 但 $A[i] = 1 < 2$ → 矛盾

因此不可行。

---

二、算法设计

2.1 算法框架

基于上述数学分析，算法设计如下：

阶段 1：贪心模拟

• 重复以下操作直到最大差值 $< 2$：
  1. 找到差值最大的房子作为起点
  2. 从起点开始，按环形顺序对每个房子执行汇款操作
  3. 更新最大差值

阶段 2：最终状态判定

• 如果所有 $A[i] = B[i]$ → 输出 Yes
• 如果所有 $A[i] - B[i] = 1$ 且存在 $B[i] > 0$ → 输出 Yes
• 否则 → 输出 No

---

2.2 贪心策略的优化

为什么从差值最大的房子开始？

引理 3：从差值最大的房子开始绕环汇款，可以最快地减小全局最大差值。

直观理解：

• 差值最大的房子有最多的"多余钱"
• 优先处理它可以让更多的钱进入流通
• 在环形结构中，钱会沿着环传递，逐步平衡

数学分析： 设起点为 $s$，经过一轮汇款后：

• $d[s]$ 减小到 $\le 1$
• 路径上的其他房子可能接收到来自前一个房子的汇款
• 总体效果：差值被"平滑化"

---

三、代码模块详解

模块 1：全局变量与宏定义

namespace yhy {
const int MAXN = 1e6 + 5;
#define int long long
int a[MAXN], b[MAXN];
int n;

设计说明：

• MAXN：最大房子数量
• #define int long long：防止溢出（$A_i, B_i \le 10^9$）
• a[]：当前金额数组
• b[]：目标金额数组
• n：房子数量

---

模块 2：汇款操作函数

inline void Change(int u, int v) {
    int x = a[u] - b[u];  // 计算差值
    
    if (x <= 0)
        return;  // 如果没有多余，不汇款
    
    x /= 2;           // 汇款金额 = 差值的一半（向下取整）
    a[u] -= x * 2;    // 房子u减少 2x（汇款 + 手续费）
    a[v] += x;        // 房子v增加 x
}

操作解析：

步骤 1：计算差值

int x = a[u] - b[u];

$x$ 表示房子 $u$ 比目标多出的金额。

步骤 2：判断是否需要汇款

if (x <= 0) return;

如果 $x \le 0$，说明房子 $u$ 没有多余或者缺钱，无需/无法汇款。

步骤 3：计算汇款金额

x /= 2;

根据引理 1，最优汇款金额为 $\lfloor x / 2 \rfloor$。

步骤 4：执行汇款

a[u] -= x * 2;  // 房子u支付 2x
a[v] += x;      // 房子v接收 x

数学验证：

• 汇款前：$a[u] - b[u] = x_{\text{old}}$
• 汇款后：$a[u] - b[u] = x_{\text{old}} - 2 \lfloor x_{\text{old}} / 2 \rfloor$
  • 若 $x_{\text{old}}$ 是偶数：新差值 = 0
  • 若 $x_{\text{old}}$ 是奇数：新差值 = 1

---

模块 3：读入与初始化

cin >> n;
int Maxx = 0;
int id = 0;

for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    
    if (a[i] - b[i] > Maxx) {
        Maxx = a[i] - b[i];
        id = i;
    }
}

功能：

1. 读入房子数量 $n$
2. 读入每个房子的当前金额 $a[i]$ 和目标金额 $b[i]$
3. 找到初始差值最大的房子：
   • Maxx：最大差值
   • id：差值最大的房子编号

---

模块 4：贪心模拟主循环

while (Maxx >= 2) {
    // 从起点id开始，绕环汇款
    for (int i = id; i < n; i++) {
        Change(i, i + 1);
    }
    Change(n, 1);  // 房子n汇款给房子1（环形）
    
    for (int i = 1; i < id; i++) {
        Change(i, i + 1);
    }
    
    // 重新计算最大差值和对应房子
    Maxx = id = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] - b[i] > Maxx) {
            Maxx = a[i] - b[i];
            id = i;
        }
    }
}

算法流程：

外层循环：while (Maxx >= 2)

• 当最大差值 $\ge 2$ 时，继续模拟
• 当最大差值 $< 2$ 时，停止（无法再有效汇款）

内层循环 1：从起点到末尾

for (int i = id; i < n; i++) {
    Change(i, i + 1);
}

从房子 id 开始，按顺序汇款到房子 $n$。

环形连接：

Change(n, 1);

房子 $n$ 汇款给房子 $1$（形成环）。

内层循环 2：从开头到起点

for (int i = 1; i < id; i++) {
    Change(i, i + 1);
}

从房子 $1$ 到房子 id-1，完成整个环的汇款。

更新最大差值：

Maxx = id = 0;
for (int i = 1; i <= n; i++) {
    if (a[i] - b[i] > Maxx) {
        Maxx = a[i] - b[i];
        id = i;
    }
}

计算新的最大差值和对应房子，为下一轮做准备。

为什么这样绕环？

• 从差值最大的房子开始，可以最快地传递"多余的钱"
• 按环形顺序汇款，确保每个房子都有机会处理多余的钱
• 一轮汇款后，差值分布会更加平衡

---

模块 5：最终状态判定

// 判定1：是否所有房子都达到目标
int flag = 1;
for (int i = 1; i <= n; i++) {
    if (a[i] != b[i]) {
        flag = 0;
        break;
    }
}

if (flag) {
    cout << "Yes\n";
    return 0;
}

第一个判定：所有 $a[i] = b[i]$

• 如果成立，说明完美达到目标 → 输出 Yes

---

// 判定2：是否所有房子都多1元，且至少有一个期望>0
flag = 1;
int flag1 = 0;

for (int i = 1; i <= n; i++) {
    if (a[i] - b[i] != 1) {
        flag = 0;  // 不是所有房子都多1
    }
    
    if (b[i] > 0) {
        flag1 = 1;  // 存在期望>0的房子
    }
}

if (flag && flag1) {
    cout << "Yes\n";
    return 0;
}

第二个判定：所有 $a[i] - b[i] = 1$ 且存在 $b[i] > 0$

• flag = 1：所有房子都恰好多 1 元
• flag1 = 1：至少有一个房子的期望 $> 0$
• 根据定理 1，这种情况可行 → 输出 Yes

---

cout << "No\n";
return 0;

默认判定：其他所有情况都不可行 → 输出 No

包括的情况：

• 部分房子差值为 1，部分为 0
• 所有房子差值为 1，但所有期望都为 0
• 存在差值 $\ge 2$ 的房子（理论上不应该出现）

---

四、正确性证明

4.1 算法收敛性

定理 2：算法一定会在有限步内终止。

证明：

定义势函数：

$$\Phi = \sum_{i=1}^{N} d[i]^2$$

引理 4：每轮操作后，$\Phi$ 严格递减或者最大差值减小。

证明： 考虑一次汇款操作 Change(u, v)，设汇款金额为 $x$。

汇款前：

$$\Phi_{\text{before}} = \cdots + d[u]^2 + d[v]^2 + \cdots $$

汇款后：

$$\Phi_{\text{after}} = \cdots + (d[u] - 2x)^2 + (d[v] + x)^2 + \cdots $$

变化量：

$$\begin{aligned} \Delta \Phi &= (d[u] - 2x)^2 + (d[v] + x)^2 - d[u]^2 - d[v]^2 \\ &= d[u]^2 - 4x \cdot d[u] + 4x^2 + d[v]^2 + 2x \cdot d[v] + x^2 - d[u]^2 - d[v]^2 \\ &= 5x^2 - 4x \cdot d[u] + 2x \cdot d[v] \\ &= x(5x - 4d[u] + 2d[v]) \end{aligned} $$

由于 $x = \lfloor d[u] / 2 \rfloor$：

• 如果 $d[u]$ 是偶数：$x = d[u] / 2$

  $$\Delta \Phi = \frac{d[u]}{2}(5 \cdot \frac{d[u]}{2} - 4d[u] + 2d[v]) = \frac{d[u]}{2}(\frac{5d[u]}{2} - 4d[u] + 2d[v]) = \frac{d[u]}{2}(-\frac{3d[u]}{2} + 2d[v]) $$

  如果 $d[v] < \frac{3d[u]}{4}$，则 $\Delta \Phi < 0$

在环形结构中，通过多轮传递，势函数会逐步减小，最终收敛。

更简单的论证：

• 每轮操作后，最大差值要么减小，要么保持
• 但不会持续保持（因为在环中传递会平衡差值）
• 因此最终会收敛到最大差值 $< 2$

---

4.2 最终判定的正确性

定理 3：算法的最终判定正确。

证明：

当算法终止时，所有 $d[i] \in \{0, 1\}$。

情况 1：所有 $d[i] = 0$

• 显然可行

情况 2：存在部分 $d[i] = 1$

• 如果不是所有 $d[i] = 1$，则存在 $d[j] = 0$
• 此时无法通过汇款让 $d[i] = 1$ 的房子变为 0
  • 因为汇款至少让差值减少 2（汇款 1 元需要 2 元）
  • $d[i] = 1$ 无法汇款
• 因此不可行

情况 3：所有 $d[i] = 1$

• 根据定理 1：
  • 如果存在 $B[i] > 0$，可行
  • 否则不可行

因此算法判定正确。

---

五、复杂度分析

5.1 时间复杂度

单轮操作：

• 遍历所有 $N$ 个房子：$O(N)$
• 每个房子执行汇款：$O(1)$
• 重新计算最大差值：$O(N)$
• 单轮总复杂度：$O(N)$

轮数上界：

引理 5：算法的轮数是 $O(\log V)$，其中 $V = \max_i A[i]$。

证明： 每轮操作后，最大差值至少减半（在大多数情况下）。

更精确的分析：

• 初始最大差值 $\le 10^9$
• 每轮至少减半
• 因此轮数 $\le \log_2(10^9) \approx 30$

总时间复杂度：$O(N \log V) = O(N \times 30) = O(N)$

对于 $N \le 10^6$，约为 $3 \times 10^7$ 次操作，完全可行。

---

5.2 空间复杂度

• 数组 a[], b[]：$O(N)$
• 其他变量：$O(1)$

总空间复杂度：$O(N)$

---

六、算法优化与扩展

6.1 可能的优化

1. 早停优化

   • 在每轮检查是否已经达到目标状态
   • 可以提前终止

2. 差值数组优化

   • 显式维护 $d[i] = a[i] - b[i]$
   • 避免重复计算

3. 最大值维护优化

   • 使用堆或优先队列维护最大差值
   • 避免每轮遍历所有房子

但对于本题的数据规模，这些优化不是必需的。

---

6.2 算法的局限性

适用条件：

• 环形结构
• 单向汇款
• 手续费等于汇款金额

不适用场景：

• 双向汇款
• 变化的手续费
• 非环形结构

---

6.3 相关问题与扩展

1. 变种问题

   • 手续费为汇款金额的 $k$ 倍
   • 允许双向汇款
   • 多个环形结构

2. 理论问题

   • 最少汇款次数
   • 最优汇款顺序
   • 可行性的充要条件

---

七、知识点总结

7.1 核心算法技巧

1. ✅ 模拟

   • 模拟汇款过程
   • 迭代直到收敛

2. ✅ 贪心

   • 优先处理差值最大的房子
   • 汇出差值的一半

3. ✅ 数学分析

   • 差值变化规律
   • 收敛性证明
   • 特殊状态判定

4. ✅ 环形结构处理

   • 从任意点开始绕环
   • 处理边界（房子 $n$ 到房子 $1$）

---

八、总结

8.1 算法精髓

本题采用的贪心模拟 + 数学分析算法的核心思想：

1. 贪心策略：优先处理差值最大的房子，加速收敛
2. 模拟过程：按环形顺序汇款，让差值逐步平衡
3. 收敛判定：当最大差值 $< 2$ 时停止
4. 数学性质：利用"所有房子都多 1 元"的特殊性质判定可行性

---

8.2 学习价值

通过这道题，我们学习了：

1. 如何通过数学分析简化问题
2. 贪心策略在模拟问题中的应用
3. 收敛性的证明方法
4. 环形结构的处理技巧
5. 特殊状态的深入分析