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

Question

Harshith is the president of TollClub. He tasks his subordinate Aryan to oversee a toll plaza with $n$ lanes. Initially, the $i$ -th lane has $a_i$ cars waiting in a queue. Exactly one car from the front of each lane passes through the toll every second.

The angriness of a car is defined as the number of seconds it had to wait before passing through the toll. Consider it takes 1 sec for each car to pass the toll, i.e., the first car in a lane has angriness $1$ , the second car has angriness $2$ , and so on.

To reduce congestion and frustration, cars are allowed to switch lanes. A car can instantly move to the back of any other lane at any time. However, changing lanes increases its angriness by an additional $k$ units due to the confusion caused by the lane change.

Harshith, being the awesome person he is, wants to help the drivers by minimising the total angriness of all cars. He asks Aryan to do so or get fired. Aryan is allowed to change lanes of any car anytime (possibly zero), but his goal is to find the minimum possible total angriness if the lane changes are done optimally. Help Aryan retain his job by determining the minimum angriness he can achieve.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le k \le 10^6$ ) — the number of lanes and the increment in angriness on a lane change.

The second line of each test case contains $n$ space-separated integers, denoting array $a$ — the $i$ -th number representing the number of cars in the $i$ -th lane ( $1 \le a_i \le 10^6$ ).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

Note that the sum of $\max a_i$ over all test cases is not bounded.

Output

For each test case, output a single integer in a new line, denoting the minimum total angriness.

Example
InputCopy
6
3 4
13 7 4
4 9
6 12 14 5
5 3
2 4 13 5 10
1 7
6
13 4
10 26 34 39 9 43 48 41 1 38 13 4 46
16 3
176342 171863 70145 80835 160257 136105 78541 100795 114461 45482 68210 51656 29593 8750 173743 156063
OutputCopy
123
219
156
21
5315
82302351405

Note

In the first test case, Aryan shifts two cars from lane $1$ to lane $3$ , after which the array becomes $[11, 7, 6]$ . The total angriness is $\frac{11\cdot 12}{2}+\frac{7\cdot 8}{2}+\frac{6\cdot 7}{2}+2\cdot 4=123$ . It can be proven that this is the minimum possible angriness.

In the fourth test case, there is only one lane, so cars can't shift lanes. Total angriness is $\frac{6\cdot7}{2}=21$ .中文c++回答。

Answer 1

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

思路（中文）

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

\sum_{j=1}^n\frac{b_j(b_j+1)}2 \;+\;k\cdot m.

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

g_j(x)= \begin{cases} x, & x\le a_j,\\ x+k, & x> a_j. \end{cases}

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

C(\lambda)=\sum_{j=1}^n\#\{x:g_j(x)\le\lambda\}\;\ge 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)$ 足够高效。

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

Domanda

Pensiero

Considering optimal lane redistribution

Optimizing lane redistribution

Optimizing job redistribution across lanes

Balancing final assignments and minimizing cost

Minimizing waiting times and assignment cost

Risposta

Condividi questa Q&A