Harshith is the president of TollClub. He tasks hi...

下面给出思路与 C++ 实现。

思路（中文）

我们可以把所有车辆在时刻 0 直接重新分配到 n 条车道：每辆车若保留在原道，则等待时间等于它在该道的新排队位置；若改道，则在新道排到队尾，等待时间加上额外的 k 的“混乱惩罚”。记各道最终分到的车辆数为 $b_j$，满足 $\sum b_j=N$（$N=\sum a_i$），将改道的车辆数记为 $m$。总愤怒度可写成

这个问题是“可分配凸代价”的经典模型，对每个车道，第 $x$ 辆车的边际成本（增量愤怒度）为

要最小化总成本，就相当于在所有 $n$ 个序列 $\{g_j(1),g_j(2),\dots\}$ 中取前 $N$ 小的增量之和。令阈值 $\lambda$ 为第 $N$ 小的位置，即满足

并且对于 $\lambda-1$ 时不满足。二分 $\lambda$（它的范围在 $[0,\max a_i+k]$ 之内）即可找到最小的满足条件的 $\lambda$。找出 $\lambda$ 后，再在线性时间内累加所有小于等于 $\lambda$ 的增量之和，再减去多余的 $(C(\lambda)-N)$ 个值（均为 $\lambda$）即可得到答案。

整体复杂度 $O(n\log(\max a_i+k))$，满足 $n\le2\cdot10^5$、$a_i,k\le10^6$ 的要求。

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n;
        ll k;
        cin >> n >> k;
        vector<ll> a(n);
        ll N = 0, maxa = 0;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            N += a[i];
            maxa = max(maxa, a[i]);
        }

        // 二分 lambda
        ll low = 0, high = maxa + k;
        while(low < high){
            ll mid = (low + high) >> 1;
            // 计算 C(mid)
            ll cnt = 0;
            for(int i = 0; i < n; i++){
                if(mid <= a[i]) cnt += mid;
                else if(mid <= a[i] + k) cnt += a[i];
                else cnt += (mid - k);
                if(cnt >= N) break;
            }
            if(cnt < N) low = mid + 1;
            else high = mid;
        }
        ll lam = low;

        // 计算 C(lambda) 和 S_total(lambda)
        ll C_lambda = 0;
        i128 S_total = 0;
        for(int i = 0; i < n; i++){
            ll ai = a[i];
            if(lam <= ai){
                // 全部取免费部分
                C_lambda += lam;
                S_total += (i128)lam * (lam + 1) / 2;
            }
            else if(lam <= ai + k){
                // 只能取 ai 个免费
                C_lambda += ai;
                S_total += (i128)ai * (ai + 1) / 2;
            }
            else{
                // 免费 ai 个 + 付费部分 lam-k-ai 个
                ll mj = lam - k - ai; // 付费部分的长度
                C_lambda += (ai + mj);
                // 免费部分
                i128 free_sum = (i128)ai * (ai + 1) / 2;
                // 付费部分：sum_{d=1..mj} (ai + d + k)
                // = sum_{x=ai+1..ai+mj} x + k*mj
                i128 exp_x = (i128)(2*ai + mj + 1) * mj / 2;
                i128 exp_sum = exp_x + (i128)k * mj;
                S_total += free_sum + exp_sum;
            }
        }

        // 多余的 C(lambda)-N 个增量均为 lam，需要减去
        ll R = C_lambda - N;
        i128 ans128 = S_total - (i128)R * lam;

        // 输出 i128
        ll answer = (ll)ans128;
        cout << answer << "\n";
    }

    return 0;
}

复杂度分析

• 对每个测试用例，先 $O(n)$ 扫描求和和找最大 $a_i$；
• 二分搜索 $\lambda$ 范围在 $[0,\max a_i+k]$，长度至多 $2\times10^6$，二分约 21 次，每次 $O(n)$ 计算总计数 $C(\lambda)$；
• 最后一次线性 $O(n)$ 计算总愤怒度。

总体 $O\bigl(n\log(\max a_i+k)\bigr)$ 足够高效。