题目大意

有 $n$ 个烤箱，每个烤箱 $i$ 每秒会产出 $a_i$ 个蛋糕。Maple 每秒只能从一个烤箱收集一次蛋糕。如果她在某一秒收集烤箱 $i$，则只能获得自上一次收集该烤箱以来累积的蛋糕。

题目要求在 $t$ 秒内（或最后 $t$ 秒策略内）最大化收集的蛋糕总数。

题解思路（逆向思维）

这是一个典型的排序不等式与贪心策略问题。

1. 关键性质分析 根据题意，一个烤箱 $i$ 产出的蛋糕数量取决于 Maple 上一次访问它的时间间隔。如果我们考虑时间从后往前倒推，我们可以自由安排最后 $\min(n, t)$ 秒去访问哪些烤箱。

假设我们确定了最后 $t$ 秒（由于只有 $n$ 个烤箱，有效操作次数不超过 $\min(n, t)$ 次）访问烤箱的顺序为 $p_1, p_2, \dots, p_{\min(n, t)}$：

• 在倒数第 $1$ 秒（即第 $t$ 秒），访问烤箱 $p_1$。假设之前没来过，它积累了 $t$ 秒的蛋糕，产出为 $a_{p_1} \times t$。但根据代码逻辑 max(0, t - i)，我们更严谨地从数学归纳看：
• 在倒数第 $2$ 秒（第 $t-1$ 秒），访问烤箱 $p_2$，产出为 $a_{p_2} \times (t-1)$。
• 以此类推，对于倒数第 $i$ 秒访问的烤箱 $p_i$，其产出乘数因子为 $\max(0, t - i + 1)$。

2. 贪心策略的数学证明 我们希望最大化总蛋糕数：

$$\text{Total} = \sum_{i=1}^{n} a_{p_i} \cdot \max(0, t - i + 1) $$

根据排序不等式（Rearrangement Inequality）：

逆序和 $\le$ 乱序和 $\le$ 顺序和。

这里乘数因子 $\max(0, t - i + 1)$ 是随着 $i$ 增大而递减的序列（或者尾部为 $0$）。为了让乘积之和最大，我们应该将较大的 $a_i$ 分配给较大的乘数因子。

因此，最优策略是：

1. 将数组 $a$ 降序排列。
2. 最大的 $a_1$ 对应乘数 $t$。
3. 第二大的 $a_2$ 对应乘数 $t-1$。
4. ...
5. 当 $t - i + 1 \le 0$ 时，乘数为 $0$，表示剩余时间不足以让该烤箱产出一块蛋糕（或者说没有机会再去收取了）。

3. 最终公式 设排序后的序列仍记为 $a_1 \ge a_2 \ge \dots \ge a_n$，答案计算公式为：

$$\text{Ans} = \sum_{i=1}^{n} \left( a_i \cdot \max(0, t - i + 1) \right) $$

复杂度分析

• 时间复杂度：排序占用 $O(n \log n)$，求和遍历 $O(n)$。总复杂度为 $O(n \log n)$。
• 空间复杂度：存储数组 $a$ 需要 $O(n)$ 额外空间。

标准代码（C++）

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

void solve(){
    int n, t;
    cin >> n >> t;
    ll ans = 0;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    // 降序排序：将产蛋糕多的烤箱放在前面（对应更大的时间乘数）
    sort(a.begin(), a.end(), greater<int>());
    
    for(int i = 0; i < n; i++) {
        // 乘数为 max(0, t - i)
        ans += 1ll * a[i] * max(0, t - i);
    }
    
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int TC;
    cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

问题重述

我们有 $n$ 个烤炉，第 $i$ 个烤炉每秒生产 $a_i$ 个蛋糕。
在 $m$ 秒内的每一秒结束时，我们可以传送到任意一个烤炉（可以重复访问同一个烤炉），并取走该烤炉中当前积累的所有蛋糕。
问：$m$ 秒内最多能收集到多少蛋糕？

---

关键观察

1. 每个烤炉的贡献只取决于最后一次访问的时间
   因为如果我们在某个烤炉最后一次访问之后还去访问它，那么它积累的蛋糕会被取走，但后续它还会继续生产，所以最后一次访问决定了该烤炉被取走的总量。

2. 最优策略中，最后 $\min(m, n)$ 秒应该访问不同的烤炉
   因为如果我们重复访问同一个烤炉，就浪费了一次访问机会（这个访问可以用于另一个烤炉，从而获得更多蛋糕）。
   因此，在最优方案中，最后 $\min(m, n)$ 秒，每一秒访问一个不同的烤炉。

3. 反向思考
   设我们安排一个访问顺序 $p_1, p_2, \dots, p_k$（其中 $k = \min(m, n)$），表示：

   • 在第 $m$ 秒结束时访问烤炉 $p_1$（最后一次访问）
   • 在第 $m-1$ 秒结束时访问烤炉 $p_2$
   • ……
   • 在第 $m - k + 1$ 秒结束时访问烤炉 $p_k$

   对于顺序中的第 $i$ 个烤炉 $p_i$，它从上次被清空（或从第 1 秒开始）到被访问的时间长度为： [ \max(0, m - i + 1) ] 因为：

   • 如果 $i \le m$，它在第 $m-i+1$ 秒结束时被访问，所以积累了 $m-i+1$ 秒的蛋糕。
   • 如果 $i > m$，则它从未被访问，贡献为 $0$。

   因此该烤炉贡献的蛋糕数为： [ a_{p_i} \cdot \max(0, m - i + 1) ]

4. 贪心分配
   为了最大化总和，应该让生产速度 $a_i$ 大的烤炉获得更大的时间乘数 $\max(0, m - i + 1)$。
   由于乘数随 $i$ 增大而减小（$i=1$ 时乘数最大，$i=k$ 时乘数最小），我们应该将 $a_i$ 从大到小排序，然后依次分配给 $i=1,2,\dots,k$。

---

算法步骤

1. 读入 $n, m$ 和数组 $a$。
2. 将 $a$ 按非递增排序。
3. 初始化答案 $\text{ans} = 0$。
4. 对于 $i = 0$ 到 $n-1$（对应顺序中的第 $i+1$ 个烤炉）： [ \text{ans} \ += a[i] \cdot \max(0, m - i) ] 注意这里 $i$ 从 0 开始，所以乘数为 $\max(0, m - i)$。
5. 输出 $\text{ans}$。

---

数学表达

设排序后的数组为 $a_{(1)} \ge a_{(2)} \ge \dots \ge a_{(n)}$，则答案为： [ \text{ans} = \sum_{i=1}^{n} a_{(i)} \cdot \max(0, m - i + 1) ] 或等价地： [ \text{ans} = \sum_{i=1}^{\min(m, n)} a_{(i)} \cdot (m - i + 1) ]

---

示例验证

示例 1

$n=3, m=4, a=[1,2,3]$
排序后：$[3,2,1]$
计算：

• $i=1$：$3 \cdot \max(0,4-1+1)=3 \cdot 4 = 12$
• $i=2$：$2 \cdot \max(0,4-2+1)=2 \cdot 3 = 6$
• $i=3$：$1 \cdot \max(0,4-3+1)=1 \cdot 2 = 2$
  总和：$12+6+2=20$，与样例一致。

示例 2

$n=3, m=2, a=[1,2,3]$
排序后：$[3,2,1]$

• $i=1$：$3 \cdot \max(0,2)=3 \cdot 2 = 6$
• $i=2$：$2 \cdot \max(0,1)=2 \cdot 1 = 2$
• $i=3$：$1 \cdot \max(0,0)=0$
  总和：$8$，与样例一致。

示例 3

$n=1, m=1000, a=[100000]$
排序后：$[100000]$

• $i=1$：$100000 \cdot \max(0,1000)=100000 \cdot 1000 = 10^8$
  总和：$10^8$，与样例一致。

---

复杂度分析

• 排序：$O(n \log n)$
• 求和：$O(n)$
• 总复杂度：$O(n \log n)$，满足 $n$ 总和 $\le 2 \times 10^5$ 的要求。

---

代码实现（C++）

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    sort(a.begin(), a.end(), greater<int>());
    
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += 1ll * a[i] * max(0, m - i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

题目详解

问题重述

我们有 $n$ 个烤炉，第 $i$ 个烤炉每秒生产 $a_i$ 个蛋糕。
在 $m$ 秒内的每一秒结束时，我们可以传送到任意一个烤炉（可以重复访问同一个烤炉），并取走该烤炉中当前积累的所有蛋糕。
问：$m$ 秒内最多能收集到多少蛋糕？

---

关键观察

1. 每个烤炉的贡献只取决于最后一次访问的时间
   因为如果我们在某个烤炉最后一次访问之后还去访问它，那么它积累的蛋糕会被取走，但后续它还会继续生产，所以最后一次访问决定了该烤炉被取走的总量。

2. 最优策略中，最后 $\min(m, n)$ 秒应该访问不同的烤炉
   因为如果我们重复访问同一个烤炉，就浪费了一次访问机会（这个访问可以用于另一个烤炉，从而获得更多蛋糕）。
   因此，在最优方案中，最后 $\min(m, n)$ 秒，每一秒访问一个不同的烤炉。

3. 反向思考
   设我们安排一个访问顺序 $p_1, p_2, \dots, p_k$（其中 $k = \min(m, n)$），表示：

   • 在第 $m$ 秒结束时访问烤炉 $p_1$（最后一次访问）
   • 在第 $m-1$ 秒结束时访问烤炉 $p_2$
   • ……
   • 在第 $m - k + 1$ 秒结束时访问烤炉 $p_k$

   对于顺序中的第 $i$ 个烤炉 $p_i$，它从上次被清空（或从第 1 秒开始）到被访问的时间长度为： [ \max(0, m - i + 1) ] 因为：

   • 如果 $i \le m$，它在第 $m-i+1$ 秒结束时被访问，所以积累了 $m-i+1$ 秒的蛋糕。
   • 如果 $i > m$，则它从未被访问，贡献为 0。

   因此该烤炉贡献的蛋糕数为： [ a_{p_i} \cdot \max(0, m - i + 1) ]

4. 贪心分配
   为了最大化总和，应该让生产速度 $a_i$ 大的烤炉获得更大的时间乘数 $\max(0, m - i + 1)$。
   由于乘数随 $i$ 增大而减小（$i=1$ 时乘数最大，$i=k$ 时乘数最小），我们应该将 $a_i$ 从大到小排序，然后依次分配给 $i=1,2,\dots,k$。

---

算法步骤

1. 读入 $n, m$ 和数组 $a$。
2. 将 $a$ 按非递增排序。
3. 初始化答案 $\text{ans} = 0$。
4. 对于 $i = 0$ 到 $n-1$（对应顺序中的第 $i+1$ 个烤炉）： [ \text{ans} \ += a[i] \cdot \max(0, m - i) ] 注意这里 $i$ 从 0 开始，所以乘数为 $\max(0, m - i)$。
5. 输出 $\text{ans}$。

---

数学表达

设排序后的数组为 $a_{(1)} \ge a_{(2)} \ge \dots \ge a_{(n)}$，则答案为： [ \text{ans} = \sum_{i=1}^{n} a_{(i)} \cdot \max(0, m - i + 1) ] 或等价地： [ \text{ans} = \sum_{i=1}^{\min(m, n)} a_{(i)} \cdot (m - i + 1) ]

---

示例验证

示例 1

$n=3, m=4, a=[1,2,3]$
排序后：$[3,2,1]$
计算：

• $i=1$：$3 \cdot \max(0,4-1+1)=3 \cdot 4 = 12$
• $i=2$：$2 \cdot \max(0,4-2+1)=2 \cdot 3 = 6$
• $i=3$：$1 \cdot \max(0,4-3+1)=1 \cdot 2 = 2$
  总和：$12+6+2=20$，与样例一致。

示例 2

$n=3, m=2, a=[1,2,3]$
排序后：$[3,2,1]$

• $i=1$：$3 \cdot \max(0,2)=3 \cdot 2 = 6$
• $i=2$：$2 \cdot \max(0,1)=2 \cdot 1 = 2$
• $i=3$：$1 \cdot \max(0,0)=0$
  总和：$8$，与样例一致。

示例 3

$n=1, m=1000, a=[100000]$
排序后：$[100000]$

• $i=1$：$100000 \cdot \max(0,1000)=100000 \cdot 1000 = 10^8$
  总和：$10^8$，与样例一致。

---

复杂度分析

• 排序：$O(n \log n)$
• 求和：$O(n)$
• 总复杂度：$O(n \log n)$，满足 $n$ 总和 $\le 2 \times 10^5$ 的要求。

---

代码实现（C++）

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    sort(a.begin(), a.end(), greater<int>());
    
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += 1ll * a[i] * max(0, m - i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}