题解：CF2139B Cake Collection

· · 题解

CF2139B Cake Collection 题解（全题解区最短代码）

安利一下博客 🥳🎆🎉祝大家 2026 新年快乐！

纯享阅读区

题意分析

核心：用 m 秒去拿 n 个烤好的蛋糕，要拿的尽量多。用 贪心 算法。

思路引导

:::warning[提问] 如何保证能选到最好的方案？ :::

::::success[成功] 对数组 a 从大到小进行排序，如果 n \le m，则可以把所有烤箱中的蛋糕都拿一遍，生产蛋糕越多的越晚拿，且后面会给出证明：早拿一次再晚拿一次和直接晚拿一次一样，不如直接晚拿一次简单。否则 n>m，就直接拿排序后最好（a_i 较大）的烤箱中的蛋糕，同样，生产蛋糕越多的越晚拿。

综上，取个 \min \{n,m\} 即可。 :::info[Tip]{open} 从大到小进行排序不用手写 cmp 了！使用 greater<int>() 可以直接大到小进行排序。 示例代码：

sort(a+1,a+n+1,greater<int>());//对数组 a 从大到小进行排序

::: :::: :::warning[提问] 如何证明早拿一次再晚拿一次同一个烤箱，和直接晚拿一次一样？ ::: :::success[成功] 证明：
设早拿的时间为 p_1，晚拿的时间为 p_2，烤箱每秒生成 a_i 个蛋糕，早拿一次再晚拿一次可以拿走 p_1 \times a_i+(p_2-p_1) \times a_i=p_2 \times a_i，晚拿一次可以拿走 p_2 \times a_i，两式相等，故结论成立。 ::: :::warning[提问] 每拿一次可以获得多少蛋糕？ ::: :::success[成功] 由于生产蛋糕越多的越晚拿，但我们已经从大到小排序了，循环的时间却是从小到大，应该用 m-i+1 才能让下标 i 越小，生产蛋糕 a_i 越多，时间 m-i+1 越大。

因此得出 a_i 的价值为 (m-i+1)\times a_i。 ::: :::error[警告]{open} 不开 long long 见祖宗，不用 1LL 乘见祖宗。 :::

完整代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,a[200005],s;
int main(){
    cin>>t;
    while(t--){
        s=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+n+1,greater<int>());
        for(int i=1;i<=min(n,m);i++)s+=1LL*(m-i+1)*a[i];
        cout<<s<<endl;
    }
    return 0;
}
//code by _ruyingsuixing_(UID:1620655)