📝 题目大意

给定 $N$ 张卡片，每张卡片上有一个整数 $a_i$。从顶部开始，第一个人取前若干张（至少 1 张），第二个人取剩下的全部（至少 1 张）。设两人手中卡片数字总和分别为 $x$ 和 $y$，求 $|x-y|$ 的最小值。

💡 解题思路

1. 题目分析：分割点唯一确定了两人各自的卡片集合——第一个人取 $[0, i]$，第二个人取 $[i+1, N-1]$。由于每人至少取一张，合法的分割点 $i$ 满足 $0 \leq i \leq N-2$。$N$ 最大 $2 \times 10^5$，$a_i$ 的绝对值可达 $10^9$，因此总和可能达到 $2 \times 10^{14}$，必须使用 long long。

2. 算法推导：

   • 若直接枚举每个分割点并重新求和，每次需要 $O(N)$，总复杂度 $O(N^2)$ 会超时。
   • 使用前缀和优化：预处理前缀和数组 a（直接在原数组上累加），使得 a[i] 表示前 $i+1$ 张卡片的和。
   • 设总共有 sum = a[N-1]。对于分割点 $i$，第一个人和 $x = a[i]$，第二个人和 $y = sum - a[i]$。
   • 则 $|x - y| = |a[i] - (sum - a[i])| = |sum - 2 \times a[i]|$。
   • 遍历所有 $i \in [0, N-2]$，取最小值即可。复杂度 $O(N)$。

3. 边界与细节：

   • 答案初始化为 1e15（约 $10^{15}$），因为 $|sum - 2 \times a[i]|$ 理论最大约为 $4 \times 10^{14}$，$10^{15}$ 足够作为上界。
   • 循环终止条件为 i < n-1，确保第二个人至少拿到最后一张卡片。
   • 注意使用 long long（代码中为 long long int）存储前缀和、总和与答案，避免溢出。

⏱️ 复杂度分析

• 时间复杂度：前缀和计算 $O(N)$，枚举分割点 $O(N)$，总计 $O(N)$。
• 空间复杂度：仅使用一个长度为 $N$ 的数组存储前缀和，$O(N)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<long long int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    // 原地构建前缀和：a[i] 表示前 i+1 张卡片的和
    for (int i = 1; i < n; i++) a[i] += a[i - 1];
    // 总和
    long long int sum = a[n - 1];
    // 答案上界约 10^15，大于理论最大值 4e14
    long long int ans = 1e15;
    // 枚举分割点 i：第一个人取 [0, i]，第二个人取 [i+1, n-1]
    for (int i = 0; i < n - 1; i++)
        ans = min(ans, abs(sum - 2 * a[i]));
    cout << ans << endl;
}
int main() {
    solve();
    return 0;
}