1967A - 置换计数

一、题意完整翻译

有 $n$ 种卡片，第 $i$ 种卡片初始有 $a_i$ 张。 你有 $k$ 个硬币，可以一共买至多 $k$ 张卡片，随便买 $1\sim n$ 任意种类。

把所有卡片排成一长串。 定义得分： 所有长度恰好为 $n$ 的连续子数组中，恰好是 $1,2,\dots,n$ 某个排列的个数。

求：能达到的最大得分。

数据范围： $1\le t\le 100,\ 1\le n\le 2\times 10^5,\ 0\le k\le 10^{12},\ 1\le a_i\le 10^{12}$ 所有测试点 $\sum n \le 5\times 10^5$。

---

二、核心贪心结论

1. 特殊情况：所有 $a_i$ 相等，$k=0$

$$a_1=a_2=\dots=a_n$$

最优排布：循环拼接

$$[1,2,\dots,n,\;1,2,\dots,n,\;1,2,\dots,n\dots]$$

此时每一个长度为 $n$ 的窗口都是合法排列，得分拉满。

2. 一般情况关键结论

设把数组降序排列：

$$a_1\ge a_2\ge \dots \ge a_n = w$$

$w$ 是全局最小值。

令：

$$cnt=\sum_{i=1}^n [a_i = w]$$

含义：有多少个数等于最小值 $w$。

当 $k=0$ 不能再买卡片时，最大得分公式：

$$\boldsymbol{ans = n\cdot w - cnt + 1}$$

3. 为什么只有「抬高最小值」才有收益？

• 给不是最小值的卡片加数量，不会增加答案；
• 只有把当前最小值拉高，瓶颈被突破，答案才能变大；
• 所以 $k$ 个硬币必须全部优先用来抬高当前最小值。

4. $k>0$ 整体策略

1. 将数组升序排序，从小到大处理；
2. 维护当前瓶颈最小值 $w$、瓶颈个数 $cnt$；
3. 若能花光硬币把当前所有瓶颈抬到下一档数值，就抬升、合并个数；
4. 若硬币不够抬到下一档，就均分剩余硬币抬高 $w$；
5. 最后套用公式 $ans = n\cdot w - cnt + 1$ 算出最大得分。

---

三、公式详细推导

假设处理完所有购买后：

• 最终瓶颈最小值为 $w$
• 一共有 $cnt$ 个数字卡在这个最小值 $w$

能形成的合法排列窗口数量： 每一轮完整循环贡献 $n$ 个位置，受最小值限制最多有 $w$ 轮完整循环； 再扣除同最小值挤占的尾部无效区间，最终：

$$ans = n\times w - cnt + 1$$

剩余硬币处理： 设剩下硬币为 $k$：

1. 平均分给 $cnt$ 个瓶颈：

$$add = \left\lfloor \frac{k}{cnt} \right\rfloor$$ $$w \mathrel{+}= add$$

2. 余下余数 $rem=k\bmod cnt$ 有 $rem$ 个可以再多抬 $1$，不再属于严格瓶颈，所以：

$$cnt = cnt - rem$$

再代入公式即可。

---

四、算法流程一步步模拟

以样例：$n=2,k=4,\ a=[8,4]$

1. 排序：$a=[4,8]$
2. 初始：$w=4,\ cnt=1,\ i=1$
3. 下一个数 $a[1]=8$，差值 $\Delta=8-4=4$
4. 需要花费：$\Delta\times cnt = 4\times 1=4$，刚好用完 $k=4$
5. $k$ 变为 $0$，$w$ 更新为 $8$，$cnt$ 变为 $2$
6. 无剩余硬币，$rem=0$
7. 答案：$2\times 8 - 2 + 1 = 15$ 和样例输出完全一致。

---

五、C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    ll k;
    // 读入种类数 n 和硬币数 k
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    // 升序排序，从小到大处理最小值
    sort(a.begin(), a.end());

    // w：当前瓶颈最小值
    // cnt：当前有多少个数等于最小值
    ll w = a[0];
    ll cnt = 1;
    int idx = 1;

    // 贪心：尽量用 k 把最小值抬到下一个数值
    while (idx < n)
    {
        // 遇到比当前最小值大的下一档数值
        if (a[idx] != w)
        {
            // 两档之间的差值
            ll delta = a[idx] - w;
            // 把 cnt 个数全部抬升 delta 需要的花费
            ll cost = delta * cnt;

            // 硬币不够，无法抬到下一档，直接退出
            if (k < cost)
                break;

            // 足够花费，就抬升
            k -= cost;
            w = a[idx];
        }
        // 同最小值个数增加
        cnt++;
        idx++;
    }

    // 剩余硬币平均分给 cnt 个瓶颈
    ll add = k / cnt;
    ll rem = k % cnt;

    w += add;
    // 有 rem 个可以多抬 1，不再算严格瓶颈
    cnt -= rem;

    // 官方核心公式
    ll ans = w * n - cnt + 1;
    cout << ans << '\n';
}

int main()
{
    // 快读快写，防止超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

---

六、复杂度与优势

• 排序：$O(n\log n)$
• 单次遍历：$O(n)$
• 总复杂度：$O(n\log n)$ 完美满足 $\sum n\le 5\times 10^5$ 限制； 用 '\n' 不用 endl，无缓冲区刷新，不超时、不输出超限。

---