E. Klee's SUPER DUPER LARGE Array!!! - 题解

比赛与标签

比赛: Codeforces Round 971 (Div. 4) 标签: binary search, math, ternary search 难度: *1400

题目大意喵~

Klee有一个长度为 n 的数组 a，里面的元素是 [k, k+1, ..., k+n-1] 这样的连续整数。我们的任务是，从 1 到 n 中选择一个分割点 i，把数组分成两部分：[a_1, ..., a_i] 和 [a_{i+1}, ..., a_n]。

然后，我们要计算这两部分元素和的差的绝对值，也就是 x = |(a_1 + ... + a_i) - (a_{i+1} + ... + a_n)|。

目标是找到一个最合适的 i，让这个差值 x 变得最小最小，然后输出这个最小的 x 就可以啦，喵~

解题思路呐~

嘿嘿，这个问题看起来是要我们遍历所有可能的 i，然后计算和的差值，但 n 和 k 的范围可是高达 10^9 呢！直接模拟肯定会超时的说。所以，我们得找点巧妙的办法，喵！

第一步，我们来把这个复杂的式子变个身！设数组的总和是 S_total = a_1 + ... + a_n。设数组前 i 项的和是 S_i = a_1 + ... + a_i。那么，后半部分的和就是 S_total - S_i 啦。

所以，我们要最小化的 x 就变成了： x = |S_i - (S_total - S_i)| = |2 * S_i - S_total|

哇！你看，问题瞬间清晰了！我们只需要找到一个 i，让 2 * S_i 的值最接近 S_total 就行了。

接下来，我们需要计算 S_total 和 S_i。数组 a 是一个首项为 k，公差为 1 的等差数列。利用等差数列求和公式 Sum = (首项 + 末项) * 项数 / 2 或者 Sum = 项数 * 首项 + 项数 * (项数 - 1) * 公差 / 2，我们可以得到：

S_total = n * k + n * (n - 1) / 2
S_i = i * k + i * (i - 1) / 2

代入我们的目标式子，我们要找一个 i（1 <= i <= n），使得 |2 * (i * k + i * (i - 1) / 2) - S_total| 最小。化简一下 2 * S_i： 2 * S_i = 2 * i * k + i * (i - 1) = i * (2k + i - 1)

现在，我们的任务变成了：在 [1, n] 的范围内找一个 i，让 f(i) = i * (2k + i - 1) 的值最接近 S_total。

我们来观察一下这个函数 f(i) = i^2 + (2k-1)i。当 i 增大时，i^2 和 (2k-1)i 都在增大（因为 k >= 1），所以 f(i) 是一个单调递增的函数！

单调递增！这个词是不是让你想起了什么？对啦！就是二分查找！喵~

我们可以二分查找 i 的值。我们的目标是找到那个最完美的 i。由于 f(i) 是单调的，f(i) 与 S_total 的差值会先减小后增大。我们要找的就是那个“谷底”。

一个经典的二分策略是：在 [1, n] 范围内，二分查找最大的那个 i，使得 f(i) <= S_total。我们把这个 i 叫做 candidate1。

因为 f(i) 是单调递增的，所以 S_total 这个目标值一定被夹在 f(candidate1) 和 f(candidate1 + 1) 之间（如果 candidate1 + 1 不超过 n 的话）。就像这样：... <= f(candidate1) <= S_total < f(candidate1 + 1) <= ...

所以，离 S_total 最近的值，要么是 f(candidate1)，要么是 f(candidate1 + 1)。我们只需要计算这两个值和 S_total 的差的绝对值，然后取其中较小的一个就是答案啦！

总结一下步骤：

用公式计算出总和 S_total。
在 [1, n] 范围内二分查找，找到最大的 i（记为 candidate1）满足 i * (2k + i - 1) <= S_total。
考虑 candidate1 和它的邻居 candidate2 = candidate1 + 1 (如果 candidate2 <= n)。
分别计算 |f(candidate1) - S_total| 和 |f(candidate2) - S_total|。
取这两个差值的最小值，就是我们最终的答案啦！

代码实现喵~

下面就是把我们的思路变成代码的时刻！要注意 n 和 k 很大，计算过程中要用 long long 来防止溢出哦！

cpp

#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    // 提高输入输出效率，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;

        // 1. 计算数组总和 S_total
        // S_total = n*k + n*(n-1)/2
        long long S = n * k + (n * (n - 1)) / 2;

        // 2. 二分查找 i，范围是 [1, n]
        long long low = 1, high = n;
        long long candidate1 = 1; // 候选答案 i，至少是1

        while (low <= high) {
            long long mid = low + (high - low) / 2;
            
            // 计算 f(mid) = 2 * S_mid = mid * (2k + mid - 1)
            // 这里用 2LL 确保乘法在 long long 下进行，防止溢出！
            long long term = 2LL * k + mid - 1;
            long long g_mid = mid * term;

            // 如果 f(mid) 小于等于总和 S，说明 mid 可能是一个解，
            // 并且我们还可以尝试更大的 mid 来更接近 S
            if (g_mid <= S) {
                candidate1 = mid; // 更新候选答案
                low = mid + 1;    // 往右边找
            } else {
                // 如果 f(mid) 太大了，那只能往左边找
                high = mid - 1;
            }
        }

        // 3. 我们的最优解就在 candidate1 和 candidate1 + 1 之间
        long long candidate2 = candidate1 + 1;

        // 4. 计算 candidate1 对应的差值
        long long g1 = candidate1 * (2LL * k + candidate1 - 1);
        long long diff1 = llabs(g1 - S); // llabs 是 long long 的绝对值函数

        // 5. 计算 candidate2 对应的差值，注意要检查 candidate2 是否越界
        long long diff2 = LLONG_MAX; // 先设为最大值
        if (candidate2 <= n) {
            diff2 = llabs(candidate2 * (2LL * k + candidate2 - 1) - S);
        }

        // 输出两个候选差值中最小的那个
        cout << min(diff1, diff2) << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(log n) 的说。对于每个测试用例，我们都进行了一次在 [1, n] 范围上的二分查找。循环内的所有计算都是常数时间 O(1) 的，所以总的时间复杂度就是二分查找的复杂度，非常快呢！
空间复杂度: O(1) 的说。我们只用了几个变量来存储 n, k, S 和二分查找的边界，没有使用额外的数组或者数据结构，所以空间消耗非常小。

知识点与总结喵~

这道题真是一次愉快的数学和算法结合之旅呀！

核心思想：问题转化 最重要的一步就是把 |(a_1+...+a_i) - (a_{i+1}+...+a_n)| 转化成 |2*S_i - S_total|。这个转化让问题变得清晰明了，是解题的关键钥匙！
数学基础：等差数列 熟练运用等差数列求和公式是快速计算 S_total 和 S_i 的前提。数学是算法的好朋友呢！
算法应用：二分查找 当我们发现目标函数 f(i) = 2*S_i 具有单调性时，就应该立刻想到二分查找！对于“寻找最接近目标的值”这类问题，二分查找是一个非常强大的工具。通常的策略是找到一个临界点，然后检查临界点和它的邻居。
编程技巧：注意数据范围 看到 10^9 就要敲响警钟啦！计算过程中 n*k 或者 n*n 很容易超出 int 的范围，所以全程使用 long long 是非常必要的，喵~

希望这篇题解能帮助你理解这道题的奥秘！继续加油，探索更多算法的乐趣吧，喵呜~ (ฅ'ω'ฅ)

E. Klee's SUPER DUPER LARGE Array!!! - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐~ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​